728x90
[백준 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 문제의 지속적 접촉
728x90
