백준 22931 2293. 동전 1 (Python) 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 1차원 dp를 사용하여 문제를 해결할 수 있다. dp[value]는 value를 만들 수 있는 동전 조합의 수를 의미한다. dp 배열의 모든 값을 0으로 초기화하여 만든 후 dp[0]은 1로 설정한다. 이는 가치 0을 만들 수 있는 조합은 아무 동전도 사용하지 않는 하나의 경우의 수가 있기 때문이다. 문제의 점화식은 다음과 같다. value는 현재 살펴볼 가치의 합을 의미하고 coin은 현재 사용할 동전의 가치를 의미한다. dp[value + coin] +=.. 2022. 5. 15. 이전 1 다음
