문제https://www.acmicpc.net/problem/18405문제 설명 N*N 크기의 시험관이 입력으로 들어온다.시험관 배열에는 종류가 다른 바이러스들이 존재한다.바이러스의 종류는 1~K번 중 하나에 속한다. 하루가 지날 때 마다 바이러스가 상,하,좌,우로 증식된다.이 때 바이러스의 번호가 낮은 것 부터 증식한다.다른 바이러스가 존재한다면, 그 위치로는 증식하지 않는다.S초가 지났을 때, Y,X 위치에 존재하는 바이러스를 출력한다. 풀이너비 우선 탐색(BFS)는 먼저 방문한 위치들을 먼저 탐색한다. 즉 시작할 때 시험관에 존재하는 바이러스들을 오름차순으로 정렬시킨 후 큐에 입력한다면, 무조건 바이러스들은 낮은 번호부터 증식하게 될 것이다.이러한 상황에서 입력으로 받은 S초까지 BFS를 진행하..

문제https://www.acmicpc.net/problem/21775문제 설명 자원 놀이 게임을 진행한다.자원 놀이에는 3가지의 연산 카드가 존재한다.next: 아무 일도 일어나지 않고 이 카드를 버린다.acquire n: 자연수 n이 적혀진 자원 카드를 획득하려고 시도한다.: 만약 자연수 n이 적혀진 자원 카드가 공용 공간에 있다면, 자신의 공간으로 가져온 후 acquire n 카드를 버린다.: 만약 자연수 n이 적혀진 자원 카드가 누군가의 공간에 있다면, 이 카드를 버리지 않고 돌아오는 자신의 다음 차례에 재사용한다.release n: 자연수 n을 공용 공간에 반납하고 이 카드를 버린다. (카드를 버릴 수 없는 경우는 주어지지 않는다.)아래 순서로 게임이 진행된다.처음에 모든 자원 카드, 연산 ..

문제https://www.acmicpc.net/problem/3197문제 설명 R*C 크기의 호수 배열이 주어진다.배열 내 두 마리의 백조가 'L'로 주어진다.(백조가 있는 위치도 물이라고 판단한다.)배열 내 빙판 공간이 'X'로 주어진다.배열 내 물 공간이 '.'으로 주어진다.두 마리의 백조는 물 공간에서만 이동이 가능하다.1일이 지날 때 마다 물과 인접한 빙판이 녹는다. 두 백조가 서로 만나기 위해 몇 일이 걸리는지 구한다. 풀이1일차가 지나기 전 현재 물과 인접해 있는 빙판 위치를 탐색하여 Queue에 저장한다.해당 위치를 기반으로 너비 우선 탐색을 진행하여 현재 빙판이 몇 일이 걸리는 지 계산한다.이 때 다음 빙판까지 걸리는 일 수가 더 적을 때만 일 수를 갱신한다. 1일차부터 최악의 경우일 때..

문제https://www.acmicpc.net/problem/1612문제 설명자연수 N을 입력받는다.N의 배수 중에서 1만으로 이루어진 수 중에 가장 작은 수의 자릿수를 구한다.불가능한 경우 -1을 출력한다. 풀이1로만 이루어지는 수이기 때문에, N이 2와 5로 나누어지면 해당 수의 배수로는 1로만 이루어지는수를 만들수 없다.따라서 예외처리를 통해 불가능한 경우의 수를 제거했다. 1만으로 이루어 지는 수를 찾아야 하는데, 문제에서 최대 자릿 수 제한이 없어서 단순 while문으로 끝까지 찾아봤다.이론상으로는 시간 제한인 2초 내로 해결되는 것 같은데, 문제는 수의 크기였다. 자릿수가 10만대 이상으로 나오게 되면 수가 너무커지기 때문에 실행 시간은 여유로워도 너무 큰 수로 인해 연산이 느려져서 시간초과..

문제https://www.acmicpc.net/problem/2159문제 설명보나뻬띠 업체에서 N명의 고객에게 케익을 배달한다.무조건 입력 받는 고객 순서대로 배달을 진행한다. 배달을 진행할 때 고객의 인접 격자점으로 이동해도 배달이 가능하다.고객의 현 위치 또한 가능하다.모든 배달을 완료했을 때의 최단거리를 구한다. 풀이고객의 수는 최대 $N = 10^5$이다. 이때 A 고객에서 B 고객으로 이동할 때의 연산 횟수는 5*5이다.배달에는 순서가 정해져 있기 때문에 한 번의 배달을 할 때마다 25번의 연산이 주어지고, 총 $10^5$의 배달을 진행한다고 가정하면 , $25 * 10^5$의 연산이 나오기 때문에 2초라는 시간제한에 충분히 접근 가능한 풀이이다.따라서 이전 고객까지의 최단거리를 저장하고..

문제https://www.acmicpc.net/problem/2578문제 설명 5*5 크기의 빙고 판이 입력으로 주어진다. 숫자는 1~25사이로 중복없이 입력된다.사회자가 부르는 숫자 25개가 순서대로 입력된다.몇 번째 숫자를 불렀을 때 빙고가 완성되는지 검증한다. 참고로 3빙고 뿐만 아니라 그 이상의 빙고가 나와도 완성으로 판단한다. 풀이빙고판 배열의 가로, 세로, 대각선 조합을 딕셔너리의 키, 밸류로 매핑한다.사회자가 부르는 숫자를 1개씩 확인하며, 딕셔너리의 키를 순회하며 부른 숫자가 키에 존재하면 카운트를 증가시킨다.카운트가 5가되면 빙고가 완성된다. 최종 빙고의 개수를 1 증가시킨다.최종 빙고의 개수가 3개 이상이라면 함수를 종료하고 결과를 출력한다.코드import sysinput = sy..

문제https://www.acmicpc.net/problem/18500문제 설명 평면 형태의 동굴이 입력으로 주어진다.동굴에는 미네랄이 존재한다.('x')미네랄이 붙어있으면 하나의 클러스터로 판단한다.두 명의 사람이 막대기를 왼쪽,오른쪽에서 번갈아가며 던진다.던졌을 때 미네랄이 있다면 부셔진다.동시에 두 개 이상의 클러스터가 떨어지는 경우는 없다.입력으로 주어진 높이 순서대로 막대기를 던진 후 동굴의 결과 상태를 출력한다. 풀이문제 이해하기 굉장히 어려운 문제였다.예제 2번을 예시로 설명해보겠다. 초기 상태 초기 아래와 같은 동굴이 입력되고, [6,6,4,3,1] 높이 순서대로 막대기를 던진다. 높이는 아래서부터 1~8 순이다....................x.xx....xxx....xxx..

문제https://www.acmicpc.net/problem/1351문제 설명 아래 조건을 만족하는 무한 수열 A가 존재한다.$A_{0} = 1$$ A_{i} $ = $A_{\lfloor i/P \rfloor}$ + $A_{\lfloor i/Q \rfloor}$' $\lfloor x \rfloor$ = x를 넘지않는 가장 큰 정수이다.Ex) $\lfloor 3.5 \rfloor$ => 3 풀이풀이 1최초로는 단순 재귀를 통해 분할정복을 진행하다가 $A_0$이 등장했을 때 $A_0$의 값인 1을 리턴하도록 구현했지만, 시간초과가 발생했다.1번 풀이로 진행했을 때 최악의 경우 $N = 10^{12}$, $P,Q = 2$일 때 트리의 구조는 각 분기마다 $2^i$회 만큼의 실행 횟수가 생기게 된다. $1..

문제https://www.acmicpc.net/problem/14713문제 설명N마리의 앵무새가 존재한다.pps789는 cseteram에게 앵무새를 이용하여 메세지를 전달한다. 말하는 문장을 앵무새 N마리가 나누어서 기억한다.모든 앵무새가 기억하는 단어를 전부 사용하여 메세지를 완성해야 한다.앵무새들이 전달한 메세지를 전부 사용하여 문장 L을 만들 수 있는 지 검증한다.전부 사용하는 이유pps789가 보낸 메세지를 앵무새들이 나눠서 전달하는 것이기 때문에 모든 단어를 사용하여 문장을 만들어야 한다.따라서 문장을 완성했더라도 앵무새에게 단어가 남아있으면 Impossible을 출력한다. 풀이Queue를 사용해도 상관없지만, 함수를 reverse해서 Stack을 사용했다.최초에는 문장을 완성했을 때 사용하지 ..

문제https://www.acmicpc.net/problem/20112문제 설명$N*N$ 크기의 배열이 주어진다.해당 배열이 사토르 마방진인지 판별한다.가로로 읽었을 때 똑같이 읽혀야 한다.세로로 읽었을 때 똑같이 읽혀야 한다. 풀이가로 단어를 A, 세로 단어를 B에 저장한다.가로 단어를 join을 통해 저장한다.세로 단어를 for 문을 통해 한 글자씩 저장 후 join을 통해 저장한다.두 단어 A와 B가 맞는지 검증한다.코드import sysinput = sys.stdin.readlinen = int(input())board = [list(input().strip()) for _ in range(n)]for i in range(n): a = ''.join(board[i]) b = [] ..