문제 이해

n가지 종류의 동전이 있다.
동전을 활용해서 가치의 합을 k원이 되도록 만들 것이다.

이 때 경우의 수를 구하는 문제이다.

조건 1 : 동전의 개수는 제한이 없다
조건 2 : 동전의 구성은 같지만 순서가 다르면 다른 경우이다.

---

문제 풀이

문제만 읽더라도 전형적인 DP 문제라는 것을 알 수 있었다.

먼저 생각했던 방식은 아래와 같다.

1. dp[n+1][k+1]의 DP를 위한 배열을 생성한다.

2. value[n+1] 배열을 생성하고, 이 곳에 동전의 가치를 저장한다.

3. dp[t][value[t]] = 1로 설정한다.

   • t번째 동전 1개로 만들 수 있는 값은 value[t]이다. 따라서, dp[t][value[t]] = 1로 설정해 놓는다.

4. dp[i][j] = dp[i-1][j] + dp[i][j-value[i]] + dp[i][j]이다.

   • 이유 : dp[i][j]는 1 ~ i번째 동전으로 j라는 가치를 만들 수 있는 경우의 수이다. 따라서, 1 ~ (i-1)번째 동전으로 j라는 가치를 만드는 dp[i-1][j] 값과 dp[i][j-value[i]]에서 value[i]라는 새로운 i번째 동전을 추가시켜 j라는 가치를 만드는 경우의 수를 더해주면 dp[i][j]의 값을 가진다. 마지막으로, 3번에 dp[i][value[t]]에 저장한 값도 더해줘야 하므로 dp[i][j]를 더해준다.

문제는 위 방식으로 문제를 풀었을 때 메모리 초과가 발생하였다.

그런데 1 ~ 4 방식을 계속해서 생각하다보니, 굳이 dp의 크기가 $(n+1) \times (k+1)$일 필요는 없을 것 같다고 생각했다.
즉, dp의 Size를 (k+1)로 해놓는다면, dp[i-1][j]는 dp[j]를 계산할 때 원래 dp[j]에 저장되어 있는 값으로 치환할 수 있다는 것을 알 수 있었다.

따라서 이런 방법으로 dp 배열을 1차 배열로 설정하였고, 메모리 에러를 해결하면서 문제를 풀 수 있었다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static FastReader sc = new FastReader();
	
	static int n,k;
	
	public static void main(String[] args) {
		n = sc.nextInt();
		k = sc.nextInt();
		
		int[] dp = new int[k+1];
		int[] value = new int[n+1];
		
		for(int i = 1;i<n+1;i++) {
			value[i] = sc.nextInt();
			
			if(value[i]<k+1) dp[value[i]]++;
            // value[i] >= k+1일 경우 ArrayIndexOutOfBounds Error 발생
            // 아닐 경우에는 i번째 동전 1개를 사용하여 value[i] 가치를 만들
            // 수 있다. 따라서 dp[value[i]]에 1을 더해준다.
			
			for(int j =0;j<k+1;j++) {
				if(j>=value[i]) dp[j]+=dp[j-value[i]];
                // dp[j] = dp[j] + dp[j-value[i]]이다.
                // 이 때 오른쪽 식의 dp[j]는 2차원 행렬에서 dp[i-1][j]를
                // dp[j-value[i]]는 dp[i][j-value[i]]를 의미한다.
                // 또한 dp[value[i]]++은 위 수식에서 수행시켰으므로
                // i번째 동전을 사용하는 경우의 수도 포함된다.
			}
		}
		
		System.out.println(dp[k]);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 메모리 초과 : 위에서 설명했던 대로 dp를 2차원 배열로 설정했음

• 런타임 에러 : value[i] >= k+1인 경우도 존재할 것이다. 이 경우 dp의 index는 0 ~ k까지 존재하므로 ArrayIndexOutOfBounds 에러가 발생하는 것이다.