[BOJ] BOJ 2293번 '동전 1' (Java)

[백준 2293번 '동전 1']

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

 

[접근 방식]

접근 방식을 찾는데 꽤나 애를 먹었다.

가장 먼저 생각한 방식은 '거스름돈 문제' 로 대표되는 해결 방식이었다.

가장 큰 단위의 동전을 기준으로 경우의 수를 하나하나 세는 것을 생각했지만, 이를 해결하기는 무리인것 같아 실행하지 않았다.

 

DP 방식을 이용하였다.

 

DP 배열의 의미는 "dp[i] 는 합계 금액이 i 인 경우의 수를 저장한다." 이다.

코인을 하나씩 추가해 가며, 차례로 경우의 수를 누적한다.

[Java 코드]

/**
 * BOJ_2293 동전 1
 * https://www.acmicpc.net/problem/2293
 * keyword - 
 */

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

public class Main {

  static int n, k;
  static int[] coins;
  static int[] dp; //0 ~ k까지의 금액을 구성하는 방법수

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());

    coins = new int[n];
    dp = new int[k + 1];

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

    //dp
    dp[0] = 1; //아무런 동전을 사용하지 않는 경우 -> 0원이 되는 유일한 경우의 수 (초기값)

    //코인 종류를 추가해 가며 합산 금액 별 경우의 수 누적
    for (int coin : coins) {
      for (int i = coin; i <= k; i++){
        dp[i] += dp[i - coin];
      }
    }

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

 

[Rewind]

1. 어려웠던 점

- DP로 해결하는 문제임을 사전에 알았음에도 DP 배열을 어떤 의미로 구성해야 하는지 몰랐던 점 

 

2. 알게된 점

- DP 해결 문제의 한가지 대표 유형

 

3. 개선 방안

- DP 문제의 지속적 접촉