DHistory

문제 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 import sys MOD = 1000000009 t = int(sys.stdin.readline().rstrip()) d = [0] * 1000001 result = [] def solution(n): if n

문제 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split())) def solution(a): d = [1] * len(a) for i in range(1, n + 1): for j in range(1, i): if a[i] < a..

문제 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 n = int(input()) def solution(n): d = list(range(n + 1)) for i in range(1, n + 1): for j in range(int(i ** .5), 0, -1): if i == j * j: d[i] = 1 elif i > j * j: d[i] = min(d[i - j * j] + d[j * j], d[i]) return d[n] print(solution(n))..

문제 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 """ 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 5 1 1 6 15 15 6 1 1 7 21 30 21 7 1 """ n, k = map(int, input().split()) MOD = 10007 def solution(n, k): k = min(n - k, k) d = [[0] * (n + 1) for _ in range(n + 1)] d[0][0] = d[1][0] = d[1][1] = 1 for i in range(2, n + 1): for j in range(n + 1): d[i][j] =..

문제 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 풀이 """ 가장 큰 증가하는 부분 수열의 합 """ import sys from copy import deepcopy n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))[:n] def solution(a): d = deepcopy(a) for i in ra..

문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 """ d[n]: 연속된 몇 개의 수를 선택하여 가장 큰 합 """ import sys n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))[:n] def solution(a): d = [0] * len(a) for i in range(1, len(a)): d[i] = max(d[i - 1] + a[i], a[i]) ret..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))[:n] def solution(a): d = [1] * (len(a)) for i in range(2, len(numbers)): for j in range(1, ..

문제 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 """ 00 타일 1 타일 N인 모든 2진 수열을 만들 수 없다. N = 1 => 1 N = 2 => 00, 11 N = 3 => 100, 001, 111 N = 4 => 0011, 0000, 1001, 1100, 1111 2xn 타일과 동일 0 => 2x1 1 => 1x2 """ n = int(input()) MOD = 15746 def solution(n): if n == 1: return 1 a = 1 b = 2 for i in range(3, n +..

문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 """ 이친수 1. 0으로 시작하지 않는다. 2. 이친수에서 1이 "두번 연속"으로 나타나지 않는다. N자일 때, 이친수의 개수는? d[n]: n자리일 때, 0으로 끝나는 이친수의 개수 => 0과 1로 2개씩 생김 a[n]: n자리일 때, 1로 끝나는 이친수의 개수 => 다음은 0으로 끝남 """ n = int(input()) def solution(n): d = [0] * (n + 1) a = [0] * (n + 1) a[1] = 1 fo..

문제 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 """ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12 5 = 4 0 6 = 5 1 7 = 6 2 8 = 7 3 9 = 8 4 10 = 9 5 11 = 10 6 12 = 11 7 """ import sys t = int(sys.stdin.readline().rstrip()) def solution(n): if n