Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

23. 동적 계획법2

조금 더 어려운 동적 계획법 문제를 풀어 봅시다.

Java / Python

6. 동전 1

2293번

더 이상 사용되지 않는 값을 버림으로써 공간 복잡도를 향상시키는 문제. 메모리 제한에 주목하세요.

이번 문제는 n가지 종류의 동전이 있고, 각각의 동전이 나타내는 가치는 다를 때, 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하는 그 경우의 수를 구하는 문제입니다.

• Java

import java.io.*;
import java.util.*;

public class Main {
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
		StringTokenizer st = new StringTokenizer(br.readLine());           
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
        
		int[] arr = new int[N + 1];
		int[] dp = new int[K + 1];
		dp[0] = 1;
                  
		for(int i = 1; i <= N; i++) {  
			arr[i] = Integer.parseInt(br.readLine());   
			for(int j = arr[i]; j <= K; j++)
				dp[j] += dp[j - arr[i]];
		}

		bw.write(dp[K] + "\n");

		bw.flush();
		bw.close();
		br.close();
	}
}

• Python

import sys
N, K = map(int, sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for i in range(N)] # 코인의 종류
dp = [0 for i in range(K + 1)]
dp[0] = 1

for i in coin:
    for j in range(1, K + 1):
        if j - i >= 0:
            dp[j] += dp[j - i]
            
print(dp[K])