백준 2293

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

2293번: 동전 1

문제에 들어가보면 알겠지만 시간과 메모리 제한이 매우 옹졸하다.

문제 조건만 봐도 ... 괜히 2차원 배열쓰거나 반복문 크게 돌리면 분명 초과가 날 것이다... 라고 말해주고 있다.

 

원래 동적계획법 문제는 점화식을 세워버릇 했는데 이건 진짜 모르겠었다.

처음엔 그냥 동전 종류중에 가장 큰 동전의 DP 값 + 나머지 이런 식으로 분할해서 합하는건가 했는데 단순히 그렇게 종이에 계산해봤는데 답이 안 맞았다.

 

이게 예제에서는 1원, 2원, 5원 총 3종류가 주어지고, 목표 금액이 10원이었다.

동전 한 종류가지고 쭉 만드는 경우가 있을 수 있고, 2가지 사용해서 만드는 경우, 3가지 모두 사용하는 경우도 있을 수 있을것이다.

그래서 이 각각을 모두 누적시켜줘야 정답을 뽑을 수 있다.

 

표 크기 제한으로 DP[0]이 안나와있는데, 1로 걸어주면 된다. (아무 동전도 사용하지 않는 1가지 경우)

일단 1원짜리로 만들 수 있는 개수를 다 세보면 아래 표와 같다.

DP[1]	DP[2]	DP[3]	DP[4]	DP[5]	DP[6]	DP[7]	DP[8]	DP[9]	DP[10]
1	1 + DP[0]	1 + DP[1]	1 + DP[2]	1 + DP[3]	1 + DP[4]	1 + DP[5]	1+ DP[6]	1+ DP[7]	1+ DP[8]
1	2	2	3	3 + DP[0]	4 + DP[1]	4 + DP[2]	5 + DP[3]	5 + DP[4]	6 + DP[5]
1	2	2	3	4	5	6	7	8	10

여기다 2원짜리로 만들 수 있는 개수를 센다.

2원을 하나 쓰고, 나머지 금액은 이전에 계산한 값을 활용한다. 예를 들면 8원의 경우 2원짜리 하나 쓰고 나머지 2원은 DP[6]값을 더해준다. 그리고 2원의 경우 0원, 1원은 못 만드니까 이부분은 skip한다.

 

이 다음 5원짜리로 만들 수 있는 개수를 같은 방식으로 더해준다. 

그리고 마지막으로 DP[k] 출력해주면 된다. 

 

위의 내용을 코드로 바꾸면 아래와 같다. 

for (int m : money) {
	for (int i = m; i <= k; i++) {
		DP[i] += DP[i-m];
	}
}

m이 각 동전 가치이고, 반복문을 돌려가며 계속 누적시킨다고 생각하면 된다. 

 

import java.util.*;
import java.io.*;
public class p2293 {
    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[] DP = new int[k+1];
        DP[0] = 1;
        int[] money = new int[n];
        for (int i = 0; i < n; i++) {
             money[i] = Integer.parseInt(br.readLine());
        }

        for (int m : money) {
            for (int i = m; i <= k; i++) {
                DP[i] += DP[i-m];
            }
        }

        System.out.println(DP[k]);

    }
}