2293번

https://www.acmicpc.net/problem/2293

2293번: 동전 1

이번 문제는 생각하기 너무 힘들었다.. 그래서 다른 사람의 해결책을 보면서 원리를 이해했다.

이 문제에서의 핵심은 메모리를 관리하는 것이다. 그래서 동전의 사용을 dp로 저장하였다.

 

동작 방식은 먼저 0부터 k까지의 수를 만드는 과정을 기록할 배열을 둔다고 생각한다.

예를 들어 n=3 k=10이고 1,2,5가 동전으로 주어졌다고 생각해보자.(설명에서 헷갈리는 것을 줄이기 위해 동전을 one,two,five로 정의하겟다.)

0을 만들기 위해서는 아무런 동전도 필요없다. 하지만 모두 사용하지 않은 것 또한 횟수로 세어 1이라고 기록한다.

 

그 다음 1~10을 만들기위해 값이 one인 동전만을 이용해서 만들 수 있는 경우를 구한다.

그러면 dp[1,1,1,1,1,1,1,1,1,1]로 채워질 것이다. 왜냐하면, 예시로 5를 만드는데  동전 one을 5개 사용하면 되니까 1개의 경우고, 9를 만드는데는 9개를 사용하면되고...이런 식으로 하면 모두 하나의 경우를 가진다.

 

그 다음 two를 사용하는 경우를 생각해보면, two를 사용해서 만들 수 있는 값은 2~10이다.

그러면 순서대로 2의 경우는 two를 1개 사용하는 경우가 있다. 그럼 2의 값을 증가시켜 dp[1,1,2,1,1,1,1,1,1,1]로 된다.

 

3을 만드는 경우는 two 1개와 one 1개를 사용하는 경우다. 즉 two를 한개 사용하기 전의 값 즉 3-2의 자리의 경우의 수에 two 1개를 사용하는 경우를 추가해주는 것이다. 그럼 dp[1,1,2,2,1,1,1,1,1,1]이 된다. 즉 dp[3]=dp[3]+dp[3-2]인 것이다.

 

그 다음 4를 만드는 경우는 two 2개, two 1개+one 2개, one 4개의 3가지 경우가 있다. 그 중에서 two를 사용하는 경우만을 계산 하면(one만을 사용하는 경우는 이미 one을 사용하는 경우에서 구했다.)

two를 사용하는 경우는 2개 또는 1개인데, 1개를 사용하는 경우는 값2를 구하는 과정에서 저장해두었기에 이 값에 +1을 하고, two를 2개 사용하는 경우는 새로운 경우임으로 +1한다. 즉, dp[4]=dp[4]+dp[2](3=1+2)이다.

 

그 다음 5를 만드는 경우는 two 2개+one 1개, two 1개+one 3개, one 5개가 있다. 이중에서 two를 사용하는 경우만 계산하면

two를 사용하는 경우는 3에서 two를 한번 더 사용하는 경우임으로 dp[5] = dp[5]+dp[3](3=1+2)이다.

 

그리고 6의 경우는 4에서 two를 한번 더 사용하는 경우로 dp[6] = dp[6]+dp[4](4=1+3)이다.

dp[4]에는 one으로만 구한 값과 각각 two 2개, two1개와 나머지는 one으로 채워서 만든 경우를 포함하고 있다.

즉, dp[4] = two 2, two 1+one 2, one 4를 가지고 있어서 여기에 two를 추가하는 경우와 one을 추가하는 경우로 보면,

dp[6] = two 3, two 2+one 2, two 1+one 4, one 6로 구성된다.

 

그 다음 7은 dp[5]에서 two를 한번 더 사용하는 경우를 더한 값이다.

dp[5] = two 2+one 1, two 1+one 3, one 5이고, dp[7] = two 3+one1, two 2+one 3, two 1+one 5, one 7의 경우로

dp[5]에서 two를 한번 더 쓴 경우와 one만을 쓴 경우를 합한 값이다

따라서 이를 반복하면서 점화식을 세워보면 아래와 같이된다.

dp[j]=dp[j]+dp[coin[i]] (i=동전의 값, j는 만들려는 값)

 

그래서 누적합을 이용해서 코드를 짜면 아래의 정답 코드를 짤 수 있다.

package backjoon.b2293;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class b2293 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());//동전 총 갯수
        int k = Integer.parseInt(st.nextToken());//목표 금액
        int[] coin = new int[n];
        for(int i=0; i<n; i++){
            coin[i]= Integer.parseInt(br.readLine());
        }
        int[]  dp = new int[k+1];//각 자리의 값을 만들 수 있는 경우의 수 저장
        dp[0]=1;
        for(int i=0; i<n; i++){
            for(int j=coin[i]; j<=k; j++){
                dp[j]+=dp[j-coin[i]];
            }
        }
        System.out.println(dp[k]);
    }
}