CEO

문제 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제 풀이 이 문제는 위의 그림을 이해한다면 쉽게 점화식을 세울 수 있다. 처음에 N이 1일 경우, 사자가 존재하지 않을 경우와 사자가 왼쪽에 존재할 경우, 사자가 오른쪽에 존재할 경우가 각 1개씩이라는 것을 알 수 있다. N이 2가 되면 추가된 공간에 사자가 없거나, 사자가 왼쪽에 있거나, 사자가 오른쪽에 있을 경우의 수를 찾아야 한다. 새로운 공간에 사자가 없을 경우 같은 라인에 사자가 겹치거나, 모두 없어도 상관 없으므로 사자가 없는 경우, 왼쪽에 있는 경우, 오른쪽에 있는 경우를 모두 더한다. 이와 달리 사자가 왼쪽이나 오른쪽에 가기 위해서는 N - 1에 사자가 없거나, N - 1의..

1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 기존의 풀이 중 1, 2, 3 더하기와 같은 방식으로 규칙을 찾으면 n을 1, 2, 3을 더해나타낼 수 있는 경우의 수를 찾을 수 있다. 기존의 1, 2, 3 더하기 문제는 n의 범위도 작을 뿐더러 나누기 연산이 없었지만 이 문제는 범위가 1000000..

문제 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 풀이 자연수 N이 주어지면 해당 수를 제곱수들의 합으로 나타낼 때 항의 최소 개수를 구하는 문제이다. N에 따라서 항의 최소 개수를 비교하면 문제를 쉽게 풀 수 있다. N 항 항의 최소 개수 0 없음 0 1 1 ^ 2 1 2 1 ^ 2 + 1 ^ 2 2 3 1 ^ 2 + 1 ^ 2 + 1 ^ 2 3 4 2 ^ 2 1 5 2 ^ 2 + 1 ^ 2 2 6 2 ^ 2 + 1 ^ 2 + 1 ^ 2 3 7 2 ^ 2 + ..

문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 다음과 같은 조건을 통해, 한번의 계산으로 연속합 중의 최대 값을 찾을 수 있다. 현재 수열 값이 앞의 값과 더한 것 보다 값이 크면 그대로 유지하고 아닐 경우, 앞의 합산 값으로 갱신한다. 말로는 잘 이해가 안되지만 문제 예시에서 최대 값을 구하는 과정을 보면 쉽게 이해할 수 있다. Origin 10 -4 3 1 5 6 -35 12 21 Round 1 10 6 Round 2 10 6 9 Round 3 10 6 9 10 Round 4 10 6 9 10 15..

문제 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 이전에 다루었던 11053 가장 긴 증가하는 부분 수열의 풀이에서 각 원소들만 추가해주면 된다. 이는 메모이제이션을 통해 수열의 값의 크기에 따라 앞의 수 중 작은수가 얼만큼 있는지 확인할 수 있기 때문이다. 코드 from sys import stdin if __name__ == '__main__': n = int(stdin.readline()) nums = list..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 예시의 수열 10 20 10 30 20 50은 다음과 같이 가장 긴 증가하는 부분 수열을 찾을 수 있다. 앞의 수열에서 작은 수가 있는지 카운트하여, 각 값에 따라 증가하는 부분수열의 길이를 찾을 수 있다. 20 보다 작은 수가 있는가? 수열 10 20 10 30 20 50 카운트 1 2 1 1 1 1 10은 20 보다 작으므로 10의 카운트 값에서 + 1한 값을 20의..

문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 자리 수의 증가에 따라 다음과 같은 경우의 수를 확인할 수 있다. 자리 수 1 2 3 4 5 1 10 101 1000 10000 100 1001 10001 1010 10010 10100 10101 즉, N에 따라 만족하는 이친수의 경우는 f(n) = f(n - 1) + f(n - 2)라는 것을 알 수 있다. 이를 코드로 구현하면 간단히 문제를 해결 할 수 있다. 코드 if __name__ == '__main__': n = int(inp..

문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 수의 길이가 1인 경우에는 1 - 9 까지의 계단수가 있으므로 경우의 수는 9개이다. 수의 길이가 2인 경우에는 다음과 같은 경우의 수들이 있다. 시작 수 1 2 3 4 5 6 7 8 9 10 21 32 43 54 65 76 87 98 23 34 45 56 67 78 89 표를 보면 시작하는 수가 1과 9를 제외하고는 시작 수가 가질 수는 경우의 수는 다음과 같이 코드로 나타낼 수 있다. cur = [ cur[1], cur[0] + cur[2], cur[1] + cur[3], cur[2] + cur[4], cur[3] + cur[5], cur[4] + cur[6..