상상쓰

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net dp[k] = k원을 만들 수 있는 경우의 수 n번 돌 때마다 dp 배열은 갱신된다. (n번째는 n개의 수를 가지고 k원을 만들 수 있는 경우의 수) import sys n, k = map(int, sys.stdin.readline().split()) dp = [0] * (k+1) dp[0] = 1 for i in range(1, n+1): m = int(sys.stdin.readline()) fo..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 숫자 1 만으로 나타내는 방법은 각각 1가지가 있다. dp[i] = 1 다음 2 를 사용해도 된다고 하면 dp[2] = 2 이다. ((1, 1), (2)), dp[3] = 2 이다. ((1, 1, 1), (2, 1)) dp[4] 는 원래 (1, 1, 1, 1) 과 dp[4-2] 인 경우 (1, 1), (2) 에 2를 넣으면 되기 때문에..