백준 (BOJ) 2624 동전 바꿔주기 java dp

문제 링크

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

2624번: 동전 바꿔주기

 

 

 

미리 풀면 좋을 것 같은 문제: https://verycrazy.tistory.com/129

백준 (BOJ) 9084 동전 java dp

도장깨기 하듯이 같이 풀면 좋을 것 같다. 언제나 깨졌던 건 나지만

 

 

 

앞 문제랑 비슷한 접근 방식에 약간의 변형이 필요하다.

 

특정 코인(i번째)을 뽑는 것과   -   첫 번째 for문

 

만들려는 값(j)을 뽑는 것까진 같은데,   -   두 번째 for문

 

코인의 개수가 정해져 있다는 점 && 해당 코인 수를 늘려나가면서 남은 차이 값이 음수가 되지 않아야 함   -   세 번째 for문

 

 

 

세 번째 조건을 부합시키면서 경우의 수를 더해야 한다. 남은 차에 대한 dp 값이 메모이제이션돼 있으므로 재사용한다.

 

두 번째 for문에서 역 접근으로 큰 값부터 뽑아내는데 이는 dp 합의 중복을 피하기 위해서이다.

 

 

 

dp 합의 중복에 대한 단편적인 예로, i=1, j=2이고

 

dp[2] += dp[2 - 1 * 1]; 를 통해 dp[2]에는 dp[1]에 대한 값이 더해진다.

 

만약 역접근이 아닌 순방향으로 접근해서, j 값이 증가하는 방향으로 나아가면,

 

i=1, j=3이 되고,

 

위의 dp[2] += dp[1]; 실행 이후 dp[3] += dp[2];를 하게 되고 그 다음 dp[3] += dp[1]를 실행하는 상황이 생긴다.

 

이러면 결론적으로 dp[3]은 dp[1]을 두번 더하게 된다. 중복쓰.

 

이 조건 찾는데 시간이 제법 걸렸다.

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

public class Main { // 2624 다.
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        int[] coins = new int[k];
        int[] numbers = new int[k];

        for(int i=0; i<k; ++i){
            st = new StringTokenizer(br.readLine());
            coins[i] = Integer.parseInt(st.nextToken());
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[T + 1];
        dp[0] = 1;
        for(int i=0; i<k; ++i){ // i번째 코인
            for(int j=T; j>=0; --j){ // 만들려는 값 --> why 역 접근? --> 중복 방지
                for(int c=1; c<=numbers[i] && j - coins[i] * c >= 0; ++c){ // 코인의 개수가 정해져 있다는 점 && 해당 코인 수를 늘려나가면서 남은 차이 값이 음수가 되지 않아야 함
                    dp[j] += dp[j - coins[i] * c];
                }
            }
        }

        System.out.print(dp[T]);

    }
}