CEO

문제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이라면 모든 알파벳을 배울 수 ..

문제 7453번: 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주�� www.acmicpc.net 문제 풀이 앞 서 다룬 부분수열의 합 2, 두 배열의 합 합과 동일한 방식으로 푸는 문제이다. 한 줄에 A, B, C, D 4 쌍의 값이 있고 N개의 줄에 걸쳐 여러 쌍의 정수들이 주어진다. 앞의 문제들과 마찬가지로 한 번에 모든 경우를 구하는 것은 시간 초과가 발생한다. 따라서 A, B에 대한 부분합에 대한 카운트를 진행한 후, 0 - C, D의 부분합의 경우의 수를 정답으로 반영하면 ..

문제 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 문제 풀이 앞 서 다룬부분수열의 합 2와 유사한 문제이다. 부분수열의 합 2 문제는 입력되는 순열을 직접 절반으로 나누어 처리하여야 하지만, 해당 문제는 이미 A, B라는 배열을 나누어서 입력된다. 입력되는 배열을 합 중, T와 일치하는 경우가 있는지 판단하고 반환하는 문제이다. 부분수열의 합 2 문제와 동일한 로직을 통해 문제를 해결할 수 있다. 앞의 문제 처럼 배열 A에 대해 ..

문제 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 앞서 다룬 부분수열의 합 문제에서 N의 범위가 40으로 증가한 문제이다. 따라서 기존의 풀이는 이 문제에 적용할 수 없다. 시간 초과가 발생하기 때문이다. 이 문제는 한 번에 N에 대한 부분수열을 모두 구하는 것이 아닌, 수열의 좌/우측으로 나누어 부분적으로 구한 후에 좌측의 작은 값 + 우측의 큰 값부터 점차적으로 계산해 S와 만족하는지 찾게 되면 시간 안에 문제를 해결할 수 있다. def dfs(idx,..

문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 N개의 정수로 이루어진 수열에서 부분 수열의 합이 S가 되는 경우의 수를 찾는 문제이다. 이는 조합을 구하고 발생한 각 조합 중 합이 S를 만족하는지 찾으면 되는 문제이다. N의 범위가 크지 않으므로, 단순히 DFS를 사용하여 문제를 풀 수 있다. 코드 DFS를 이용한 문제 풀이 from sys import stdin def dfs(depth, subtotal): global answer if depth == ..

문제 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 www.acmicpc.net 문제 풀이 이 문제는 수들의 합 2, 부분합 문제에서 소수의 합으로 나타낼 수 있는 경우의 수를 찾는 문제이다. 연속합을 구하는 로직은 앞서 다룬 2 문제와 동일하며, 소수를 구하는 부분만 추가하면 쉽게 풀 수 있는 문제이다. 코드 from sys import stdin def is_prime(num): find = [] check = [True] * (num + 1) check[1..

문제 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 앞서 다룬 수들의 합 2와 유사한 문제이다. 다른 점이 있다면 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 것이다. 수들의 합 2와 마찬 가지로 사전에 누적합에 대한 값을 계산하고 시작, 끝 지점을 달리하여 순차적으로 탐색을 진행하면 경우의 수를 계산할 수 있다. 코드 from sys import stdin if __name__ == '__main__': answer = None start, end = 0, 1 n, s = ma..