![]()
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 동적 계획법, 그중에 상향식(Tabulation)으로 풀었다. 처음에는 백트래킹으로 풀어봤는데 시간초과가 났다. 메모리가 4MB 밖에 안 되어서 dp는 아니겠다 싶었는데 dp로 푸는 거였다. 풀이에 사용하는 변수들과 입력이다. N, K는 각각 동전 개수와 만들어야 하는 금액이며, 동전을 받기 위해 리스트를 만들어 입력해주었고, 동적 계획법으로 푸므로 dp를 0부터 K를 범위로 하는 정수 배열로 선언..
https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net # 파이썬에서는 재귀 최대 한도의 디폴트가 1000이기 때문에 더 늘려주려면 다음의 코드가 필요 import sys sys.setrecursionlimit(10 ** 7) n, k = map(int, input().split()) MOD = 10007 cache = [[0] * 1001 for _ in range(1001)] # N, K는 1부터 1000까지 이므로 이중 배열 생성 # 이항계수 nCk를 bino(n, k) 라 하면, # bino(n, k) = bino..
https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net n = int(input()) cache = [-1] * 91 # n이 최대 90이므로, 0~90까지 91개의 공간 필요. cache[0] = 0 # 피보나치 수의 F0은 0 cache[1] = 1 # 피보나치 수의 F1은 1 def fi_bottomup(n): # Tabulation, 순서 중요 for i in range(2, n + 1): # 0, 1은 미리..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net MOD = 1_000_000_000 # cache[n][d] = 길이가 n, 마지막 숫자가 d인 계단수 개수 cache = [[0] * 10 for _ in range(101)] # n은 1~100 이므로 101개를 만들고, d는 0~9까지니까 10개를 만든다. for d in range(1, 10): # cache[1][0] 은 0으로 시작하므로 문제 조건에 따라 0이다. cache[1][d] = 1 # 길이가 1이고 자릿수가 0이 아니면 초기값은 1이다. for N in range(2, 101): # 길이 ..
