[DP] 백준 2293번 동전1 - JAVA

 

간만에 스터디 DP 문제를 풀어보았습니다.

역시 DP... 익숙치 않다보니 어렵게 느껴졌습니다 ㅠㅠ

기록하며 한 번 더 풀어보는 시간을 갖겠습니다!

 

---

1. 출처

---

 

 

2293번: 동전 1

 

 

 

누가봐도 DP 문제라고 알려주는 시간 제한...

 

 

---

2. 설계

---

 

사실 다른 블로그 해석을 봐도 한 번에 와닿지는 않았습니다. 이해하는 데 시간이 걸렸어요.

다들 설계는 2중 배열로 한 것 같은데 왜 1차원 배열로 점화식을 냈지? 의문이었죠...

 

그리하여 제가 이해한 과정을 기록해봅니다...

 

1) n개의 동전을 coins 1차원 배열에 저장합니다.

for(int i=0;i<n;i++){
	coins[i] = Integer.parseInt(br.readLine());
}

 

 

2) 각 동전에 대해 1원 ~ 목표 금액을 차근히 for문을 돕니다.

 

k는 목표 금액입니다.

int[] dp = new int[k+1]; //1원부터 시작
for(int i=0;i<n;i++){ //사용 동전
	for(int j=1;j<=k;j++){ //동전으로 만들고 싶은 가격

		if(coins[i]==j) dp[j]++;

		else if(coins[i]<j){
			dp[j] += dp[j-coins[i]];
		}
	}
}

 

 

 

위 코드 과정을 이미지로 정리하자면 아래와 같습니다.

 

 

2-1) coins[i] == j -> dp[j] += 1

 

사용 동전이 coins[0] = 1원이고, for문을 돌며 j = 1원을 만들 차례라고 가정합니다.

1원을 가지고 1원을 만들 수 있으므로 dp 배열에 +1을 추가해줍니다.

즉, coins[i] == j -> dp[j] += 1 입니다.

 

이 때 dp 배열의 의미는 목표 금액을 만들 수 있는 경우의 수입니다.

 

 

2-2) coins[i] > j -> dp[j] += dp[j-coins[i]]

 

사용 동전이 coins[0] = 1원이고, for문을 돌며 j = 2원을 만들 차례라고 가정합니다.

사용 동전보다 만들고자 하는 가격이 큰 경우 coins[i]를 가지고 목표 가격을 만들 수 있는지를 확인 후 추가합니다.

 

1원을 가지고 2원을 만들려면 남은 금액 1원을 만들 수 있는 경우의 수가 몇 개인지 확인해야 합니다.

그래서 dp[2원 - 1원] = dp[1원] = 1을 확인해야 합니다.

그래서 dp[2] =0+1 = 1의 과정을 얻게 됩니다.

 

 

위 과정을 모두 거치면 coins[0] = 1원 즉, 1원을 가지고 1~10원까지 만드는 과정의 dp 배열은 다음과 같습니다.

 

 

 

이해가 안가신다고요? 그럼 coins[1] = 2원을 가지고 해보겠습니다.

 

 

2-3) 1원 후 2원을 가지고 dp 테이블의 변화를 살펴보자!

 

[시작전]

1원 연산 과정을 거친 dp 1차원 테이블을 그대로 사용합니다.

 

 

[ coins[1] , j = 1 ]

사용 동전이 coins[1] = 2원이고, for문을 돌며 j = 1원을 만들 차례라고 가정합니다.

coins[1] > j 인 상태네요. 작은 상태의 경우 아무 변화가 없습니다. 2원을 가지고 1원을 만들 수 없기 때문입니다.

 

[ coins[1] , j = 2 ]

그래서 그대로 j = 2로 이동합니다. coins[1] == j 인 상태네요. 위에서 해줬던 것처럼 +1을 해줍니다.

 

[ coins[1] , j = 3 ]

coins[1] < j 인 상태네요. 2로 3을 만들 수 있는 경우의 수를 따져줍니다.

현재 dp[3] = 1의 의미는 1로만 3원을 만들 수 있는 경우의 수가 1개라는 의미입니다.

 

그렇다면 2원을 가지고 3원을 만들 수 있는 가짓수를 더해줘야겠죠?

2원을 가지고 3원을 만들려면 1원이 부족하므로 dp[3원 - 2원] = dp[1]을 통해 2원과 1원을 가지고 3원을 만들 수 있는 방법이 1가지 있음을 확인합니다. 즉 dp[3] = 1(1원으로만 3원을 만드는 가짓수) + 1(2원과 1원을 가지고 3을 만드는 가짓수) = 2가 되겠죠.

 

 

.

.

.

 

이런식으로 쭉쭉 연산을 해나가면 coins[1] = 2원의 최종 dp 결과는 아래와 같습니다.

 

 

 

2-4) 1원, 2원 후 5원을 가지고 dp 테이블의 변화를 살펴보자!

 

5원도 같은 변화 양상을 보일 겁니다.

5원으로는 1~4원을 만들지 못하니 이전 값의 변화는 없습니다.

그러나 5원일 때 +1이 더해집니다. 5원을 가지고 5원을 만들 수 있으니까요!

 

 

.

.

.

 

쭉 5원을 이용해 타겟 금액을 계산할 방법을 더하다 보면 아래와 같은 결과를 도출합니다.

 

 

dp[10] = 10의 의미는 1,2,5원을 모두 이용해 10원을 만드는 경우의 수가 되겠죠.

 

 

---

3. 전체 코드

---

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String n_k = br.readLine();
        StringTokenizer st = new StringTokenizer(n_k, " ");
        int n = Integer.parseInt(st.nextToken()); //동전개수
        int k = Integer.parseInt(st.nextToken()); //목표금액

        int[] coins = new int[n];
        for(int i=0;i<n;i++){
            coins[i] = Integer.parseInt(br.readLine());
        }

        // 입력 끝

        int[] dp = new int[k+1]; //1원부터 시작
        for(int i=0;i<n;i++){ //사용 동전
            for(int j=1;j<=k;j++){ //동전으로 만들고 싶은 가격

                if(coins[i]==j) dp[j]++;

                else if(coins[i]<j){
                    dp[j] += dp[j-coins[i]];
                }
            }

        }

        System.out.println(dp[k]);
    }
}