투투

문제 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 입력 첫째 줄에 테스트 케이스가 입력된다. 테스트 케이스마다 한 줄에 하나씩 K와 N을 입력한다. K와 N은 1이상 14이하이다. 출력 K층 N호에 몇 명이 사는지 출력한다. 접근 처음에 문제가 잘 이해되지 않았다. 그래서 그림을 그려보면서 ..

www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 접근 1은 1칸 2~7은 2칸 8~19는 3칸 20~37은 4칸 이렇게 나열하여 규칙을 찾아보면 1 -> 7 -> 19 -> 37 에서 각 수가 증가하는 크기가 6 -> 12 ->18 이다. 따라서 처음에 1에서 6을 더하고 그 다음 12를 더하는 식으로 나아가서 찾아가야 할 칸이 그 범위에 속하면 몇 칸인지 출력한다. 구현 찾아야할 칸을 N에 입력받는다. 그리고 idx는 초기 1번을 나타내며 현재 1번에서 1번까지는 ..

문제 손님이 도착하는 대로 빈 방을 배정하고 있다. 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다. 호텔은 직사각형 모양이라고 가정하자. 각 층에 W개의 방이 잇는 h층 건물이다. 엘레베이터는 가장 왼쪽에 있다. 이런 형태의 호텔을 HxW 형태 호텔이라고 부른다. 호텔 정문은 1층 엘레베이터 바로 앞에 있다. 정문에서 엘레베이터까지의 거리는 무시하고 인접한 두방 사이의 거리는 모두 1이다. 방 번호는 YXX 또는 YYXX형태이며 Y나 YY는 층 수 XX는 엘리베이터에서부터 세웠을 때의 번호를 나타낸다. 손님은 엘레베이터를 타고 이동하는 거리는 신경쓰지 않는다. 다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다. 초기에는 모든 방이 비어있고 N번째로 도착한 손님..

문제 (x, y)에 위치해 있을 때 왼쪽 아래 꼭짓점 (0, 0) - 오른쪽 위 꼭짓점 (w, h)를 갖는 직사각형에서 경계선까지 가는 거리의 최솟값을 구하라 입력 첫째 줄에 x, y, w, h가 입력된다. w, h는 1이상 1000이하 출력 경계선까지의 최소거리를 출력한다. 접근 (x, y)에서 상하좌우의 거리만 구해보면된다. 따라서 최솟값의 후보가 될 수 있는 것은 x와 y값 그리고 w-x, h-y가 된다. 구현 min함수를 활용하여 위에서 봤던 네 개의 값을 비교하였다. x, y, w, h = map(int, input().split()) answer = min(x, min(y, min(w-x, h-y))) print(answer)

programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 접근 문제를 봤을 때 " | " 연산자가 생각이 났다. 두 개의 배열의 각각 원소를 OR 연산을 하여 맵을 출력하면 됐다. 구현 arr1과 arr2에 있는 같은 인덱스의 숫자끼리 OR연산을 하여 bin()을 통해 2진수로 변환한다. 그렇다면 앞에 0b가 붙은 문자형으로 변환이 된다. 이때 인덱스 2부터 검사를 하여 1이면 # 0이면 공백을 해주는데 전달받은 n자리를 맞..

programmers.co.kr/learn/courses/30/lessons/12901 코딩테스트 연습 - 2016년 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까 programmers.co.kr 접근 2016년의 특정 달의 특정 일을 입력받아 요일을 출력해야 한다. 이를 위해 각 달이 몇 일까지 있는지 알면 편하다. 입력받은 월 전까지의 일 수를 모두 더한다음 보고자하는 일수 b를 더하고 -1을 해준다. 여기에 7로 나눈 나머지를 취하여 days의 인덱스로 활용한다. 1월 1일부터 5월 24일까지 더한 일수를 7로 나눈 나머지가..

programmers.co.kr/learn/courses/30/lessons/12915 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1 programmers.co.kr 접근 파이썬의 sort()에 key값을 넣어서 정렬을 하였다. 만약에 n번째 숫자가 같다면 사전순으로 정렬해야하기 때문에 먼저 기본적인 sort를 진행한 후에 key값을 추가하여 n번째 글자로 정렬되도록 하였다. 구현 def solution(strings, n): answer = [] strings.sort() s..

programmers.co.kr/learn/courses/30/lessons/64061?language=python3 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 접근 스택을 이용하면 쉽게 풀 수 있을 것이라고 생각했다. 구현 스택과 보드의 길이를 생성한다. 이후 크레인의 움직이는 정보가 담긴 moves에서 정수 x를 -1로 한 후에 세로 축 탐색을 진행한다 만약 숫자가 나오고 스택이 비었다면 바로 스택에 넣고 스택이 비어있지 않다면 스택의 맨 위와 현재 정수를 비교하여 같다면 최종해 +2 (한 번에 2개가 터짐) 이후 스택의 to..

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 접근 2차원 리스트에 무방향 그래프를 표현하고 DFS를 탐색하여 연결 요소들을 찾는다. 이때 DFS가 실행된 수만큼 연결 요소의 수가 된다. 구현 정점과 간선을 입력받고 정점의 크기만큼 2차원 리스트를 생성한다. 그리고 방문표시를 위한 1차원 리스트도 생성한다. -> False로 초기화됨 N, M = map(int, input().split()) matrix = [[0 for _ in range(N)] for..

문제 피보나치 함수를 실행했을 때 0일 때와 1일 때 몇 번 실행되는지 구하라 입력 첫째 줄에 테스트 케이스가 주어지며 이어서 40이하의 수가 입력된다. 출력 테스트 케이스마다 0일 때와 1일 때 실행횟수를 공백을 두고 출력한다. 접근 처음에 재귀함수를 사용해서 풀었는데 시간초과가 발생했다. 그래서 DP에 분류가 되어있던 것 같다 DP로 접근을 했을 때 각 수에서 0과 1이 몇 번실행되는지 규칙을 찾았을 때 현재인덱스 idx에서 idx-1, idx-2의 0과 1을 누적합을 해주면 된다. 구현 테스트 케이스마다 수를 입력받고 dp를 저장할 2차원 리스트를 생성한다. 그리고 초기에 0과 1에서는 0과 1이 몇 번 실행되는지 저장해둔다. N = int(input()) dp = [[0, 0] for _ in r..