[BOJ] 2293번 동전1

개요

전형적인 DP를 이용하는 문제

문제링크

코드

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

public class Baekjoon2293 {
    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[] coin = new int[n];    //동전을 저장하는 배열  
        int[] dp = new int[k+1];    //DP테이블을 저장하는 배열(동전의 합 0~k)
        for(int i=0;i<n;i++) 
            coin[i] = Integer.parseInt(br.readLine());
        
        dp[0] = 1;  //0번째 인덱스는 1로 초기화
        for(int i=0;i<n;i++) {
            for(int j=0;j<=k;j++) {
                if(coin[i]<=j)  //동전의 합인 j가 i번째 동전보다 크거나 같을 때(동전의 합에 최소한 i번째 동전이 들어갈 수 있을 때)
                    dp[j] += dp[j-coin[i]];
            }
        }
        bw.write(dp[k]+"");
        bw.flush();
        
    }
}

해결 과정

DP 문제는 DP 테이블을 만들고 문제를 풀어나가면서 나오는 중간값들을 이용해 최종 값에 도달하는 문제이다.

문제에서 주어진 예제를 표로 그려보자

위 이미지는 동전의 합이 1~10인 경우와 [1], [1,2], [1,2,5] 동전을 사용한 경우의 표이다.

규칙을 찾아보면 동전 [1,2]를 사용할 때 2칸마다 숫자가 늘어난다. 이것을 바탕으로 식을 만들어볼 수 있다.

DP[ j ] = DP[ j ] + DP[ j - 2 ]

하지만 이식은 살짝 불안정하다. j = 2일 때는 DP[ 2 ] = DP[ 2 ] + DP[ 2 - 2 ] 으로 DP[ 0 ]이 없어서 인덱스를 벗어난게 되기 때문이다.

그래서 합이 0인 경우의 수(동전을 하나도 안썻을 경우)도 추가해주었다.

이제 위의 식을 바탕으로 확장을 해볼 수 있는데

동전 [1,2,5]를 사용할 경우를 보면

5원 짜리 동전을 사용할 수 있는 j = 5 부터 값이 증가한다. 그런데 [1,2]만 사용할 때보다 1이 늘어났고 j = 6일 경우에도 1이 늘었다.

이걸 바탕으로 추론하면 다음과 같다.

DP[ j ] = DP[ j ] + DP[ j - 5 ]

두개의 식을 가지고 점화식을 만들어보면

DP[ j ] = DP[ j ] + DP[ j - 동전값 ] ( j ≥ 동전값 )

이것을 코드로 표현하려면 DP 배열은 [n] x [k+1] 만큼의 사이즈가 필요하다

하지만 잘 생각해보면 [k+1]사이즈의 1차원 배열을 가지고도 식을 표현 할 수 있다.

이것을 코드로 표현한 것이 아래 코드이다.

for(int i=0;i<n;i++) {
    for(int j=0;j<=k;j++) {
        if(coin[i]<=j)
            dp[j] += dp[j-coin[i]];
    }
}

결과