문제 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 - 이동하고자 하는 채널)과 해당 채널의 수를 버튼으..
문제 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 풀이 학생들은 K개의 알파벳을 배울 수 있다. 이때 N개의 단어 중 가장 많은 단어를 읽을 수 있는 경우의 수를 찾는 문제이다. 문제는 다음과 같은 경우를 확인하며 DFS로 풀면 쉽게 풀 수 있다. 언어는"anta"로 시작되고, "tica"로 끝나므로 배울 수 있는 단어 중, 'a', 'c', 'i', 'n', 't'를 배워야 하므로 5를 제외한다. 만약 K가 5보다 작다면, 읽을 수 있는 단어는 없다. K가 26이라면 모든 알파벳을 배울 수 ..
