[JAVA] 백준 2293. 동전 1 :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 동적 프로그래밍을 이용한 문제를 풀어볼 예정입니다.

---

1. 문제

사진을 클릭하면 문제  페이지로 이동합니다

 

2. 입출력 예제

 

3. 접근

1. 동적 프로그래밍에서 가장 중요한 것은 해결했던 문제에 대해서 다시 문제를 풀지 않는 것이다.

2. 이전에 풀었던 문제를 메모이제이션(Memoization)을 통해 다시 계산하지 않고 결과 값만 가져온다.

* res[k] : k원을 만들 수 있는 경우의 수

* cArr[i] : i번 째 동전의 값

* res[k] += res[k - cArr[i]]

  : k원을 만들 수 있는 경우의 수에 k - cArr[i]원을 만들 수 있는 경우의 수의 합

 

[설명]

 * cArr[i]가 1원일 때, 10원을 만들기 위해서는 res[10] += res[9]

 ---> cArr[i]가 1원일 때의 res[10] = res[9] + 1원, 이전 동전으로 10원을 만드는 경우의 수 res[10]을 더하면 res[10] = res[10] + res[10 - 1] 식 도출.

 

 * cArr[i]가 2원일 때, 10원을 만들기 위해서는 res[10] += res[8]

 ---> cArr[i]가 2원일 때의 res[10] = res[8] + 2원, 이전 동전으로 10원을 만드는 경우의 수 res[10]을 더하면 res[10] = res[10] + res[10 - 2] 식 도출.

 

 * cArr[i]가 5원일 때, 10원을 만들기 위해서는 res[10] += res[5]

 ---> cArr[i]가 5원일 때의 res[10] = res[5] + 5원, 이전 동전으로 10원을 만드는 경우의 수 res[10]을 더하면 res[10] = res[10] + res[10 - 5] 식 도출.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    static int n;
    static int k;
    static int[] cArr;
    static int[] res;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        cArr = new int[n];
        res = new int[k + 1];
        
        // Coin Init
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine().trim());
            cArr[i] = Integer.parseInt(st.nextToken());
        }
        
        solveDp();
        System.out.println(res[k]);
    }
    
    private static void solveDp() {
        for(int i = 0; i < n; i++) {
            if(cArr[i] <= k) {                
                res[cArr[i]] += 1;
                
                for(int j = cArr[i] + 1; j <= k; j++) {
                    res[j] += res[j - cArr[i]];
                }
            }
        }
        return;
    }
}
 

 

5. 결과