문제 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까지의 숫자로 변환한다. 그러면,..
문제1107번: 리모컨첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼www.acmicpc.net 문제 풀이 채널 N으로 이동하고자 할 때, M개의 버튼이 고장 나서 고장 난 버튼을 제외하고 +, -를 활용하여 원하는 채널에 접근하기 위해 최소로 리모컨 버튼을 누르는 경우를 반환하는 문제이다. DFS를 통해 탐색을 진행하더라도, python3의 recursive depth를 초과하지 않으므로 DFS로 문제를 풀었다. 고장 난고장 난 버튼이 없는 경우채널 100번부터 시작하므로 abs(100 - 이동하고자 하는 채널)과 해당 채널의 수를 버튼으..
