CEO

문제 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 문제 풀이 8x8의 체스판이 있을 때, 총 9가지의 경우의 수에 따라 움직일 수 있다. 경우의 수는 상, 하, 좌, 우, 대각선 그리고 현재 위치에 그대로 있는 경우이다. 또한 다른 문제와 다른 점이 있다면 체스판이 아래로 이동하여 그래프의 상태가 변화한다는 것이다. 예를 들어 예제 입력 2의 경우는 1초의 시간이 경과하면서 벽의 위치가 다음과 같이 변화한다. current|after 1 sec ........|........ ........|....

문제 15558번: 점프 게임 첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000) 둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보�� www.acmicpc.net 문제 풀이 지도가 좌측, 우측 2개의 줄로 나뉘어 있고, 3가지의 경우로 현재 칸에서 이동할 수 있다. 첫 번째는 현재 칸에서 한 칸 앞으로 가는 것이고 두 번째는 한 칸 뒤로 가는 것이다. 마지막으로 다른 줄에서 K칸 앞으로 가는 경우가 있다. 문제를 풀기 위해서는 앞서 다룬 토마토 문제와 같이, 한 단계에서 처리 가능한 모든 경우의 수를 처리해주어야 한다. 토마토 문제와 달리 다음번 칸으로 갈 수 있는지와, 1초가 지나면 이전..

문제 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 문제 풀이 앞서 다룬, 랜선 자르기, 나무 자르기와 동일한 이분 탐색 유형의 문제이다. N개의 집이 주어 질 때, 각각의 집 사이에 C개의 공유기를 적절히 설치하는 최대 거리를 반환하는 문제이다. 예제 입력 1의 경우 1 2 4 8 9와 같이 집이 위치한다. 공유기 3대를 최대 거리로 설치하기 위해서는 3이라는 것을 알 수 있다. 이를 이분 탐색으로 찾기 위해서는 1과 마지막 집을 기준으로 이분 탐색을..

문제 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, www.acmicpc.net 문제 풀이 앞서 다룬 랜선 자르기와 동일한 방식으로 풀 수 있는 문제이다. 다른 점이 있다면, 잘리는 나무가 mid보다 큰 경우만 경우에 포함된다. 문제에 주어진 것처럼 이분 탐색으로 15라는 높이로 나무를 자른다면 20 - 15 = 5, 17 - 15 = 2, 총 7m의 나무를 가져갈 수 있다. 코드 from sys import stdin if __name__ == '__main__': k, n = map(int, stdin.readline().split(..

문제 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 K개의 랜선이 있을 때, N개의 랜선을 만들고자 하는 경우 각 랜선의 길이가 최대가 되는 경우를 반환하는 문제이다. 문제의 분류와 같이, 이분 탐색을 통해 문제를 해결할 수 있다. 이분 탐색은 start, mid, end를 통해 찾고자 하는 목표를 탐색할 수 있다. start 1, end는 가장 긴 랜선의 길이로 지정한다. mid = (start + end) // 2 주어진 랜선들을 mid로 나누고 이를 합한다. 합산..

문제 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 문제 풀이 A, B, C의 물통이 있고, 처음에는 C의 물통에만 물이 가득차 있다. 물통에 물을 한번에 다른 통으로 이동시키는 경우, A가 비어있는 경우에 C의 물통에 차있는 물의 양을 반환하는 문제이다. 물을 옮길 수 있는 경우의 수는 6가지가 존재한다. 이는 순열로 DFS나 permutaion을 이용해 구해도 되지만, `A → B`, `A → C`, `B → A`, `B → C`, `C → A`, `C → B`와 같은 경우의 수를 하..

문제 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net 문제 풀이 돌의 개수가 다른 세 개의 그룹 A, B, C가 주어 질 때 세 개의 그룹 중 2개를 선택한 후, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 한다. 이때, X에 있는 돌의 개수를 X + X로 Y에 있는 돌의 개수를 Y - X개로 만든다. 이와 같은 방식으로 모든 경우의 수를 진행하여 A, B, C의 돌의 개수가 같아지는지 여부를 반환하는 문제이다. 그룹의 돌의 개수 합이 3으로 나누어지는 경우, 돌의 개수가 같아 질 수 없다. A, B, C ..

문제 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 각 알파벳이 주어질 때, 어느 자리에 위치하느냐에 따라 0에서 9의 숫자로 변환하여 합을 계산하여야 한다. 문제를 풀기 위해서 자릿수가 가장 큰 알파벳부터 9부터 0까지 숫자를 변환하면 된다. 예를 들어 예제 입력 2의 경우 `{'A': 10000, 'C': 1010, 'G': 100, 'D': 100, 'E': 10, 'F': 1, 'B': 1}`와 같이 A, C, G, D, E, F, B 순으로 9에서 3까지의 숫자로 변환한다. 그러면,..