[백준] 9084. 동전

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

 

예전에 프로그래머스에서 비슷한 문제를 푼 적이 있는데 그 때 날림으로 풀고 지나갔더니 다시 푸니까 머리에 안개낀 기분
그래서 이번엔 확실하게 이해하려고 노력해봤다

 

 ➡️ 주어진 동전 종류를 가지고 주어진 금액을 만들 수 있는 모든 경우의 수를 구해야 한다.

 

동전 한 종류만 생각했을 때, 2원짜리 동전으로 12원을 만드는 방법은: 2+2+2+2+2+2 딱 1가지가 된다.
즉 2원을 사용해서 p원을 만드는 경우의 수는 p-2원을 만드는 방법의 개수와 같다. (일단 이게 핵심이다)

갑자기 논리 점프라고 생각할 수 있는데... 🥲 다시 차근차근 생각해보면,

12원을 만들건데 2원을 꼭 쓰고싶다면 10원+2원 구성이 된다. 그럼 12원을 만들 수 있는 경우의 수는 10원을 만들 수 있는 경우의 수다.

10원을 만들건데 2원을 꼭 쓰고싶다면?! 8원+2원 구성이 된다. 그럼 10원을 만들 수 있는 경우의 수는 8원을 만들 수 있는 경우의 수다...

 

 

생각 구체화를 위해서 예시로 좀 더 생각해보면

동전이 여러 종류인 상황을 생각했을 때는 작은 동전부터 차례로 추가하면서 경우의 수를 더해주면 된다.

동전이 2원, 4원이고 금액이 12원이라면: (1)먼저 2원짜리만으로 경우의 수를 구한 뒤에 (2)4원짜리를 추가하면서 경우의 수를 누적한다.

(1)2원만 사용했을 때: 12 = 2+2+2+2+2+2 → 1가지 10 = 2+2+2+2+2 → 1가지

(2)4원을 추가했을 때: 12 = 4+8 = 4+4+4 = 2+2+4+4 이런 식으로 경우의 수가 늘어난다.

 

😡 왜 경우의 수를 누적하냐고 

여기서 느낌상 이렇게 해야 맞는다는 건 아는데 논리적으로 설명하라고 하면 그냥…;;에서 끝나서 많이 고민했다..

 

다시 한번 생각해보면 -- 12원을 4원짜리를 추가해서 만들려면 8원짜리를 만드는 경우의 수와 같다.
8원을 만드는 경우의 수는 이미 2원과 4원으로 구해둔 경우가 2+2+2+2, 2+2+4, 4+4로 3가지니까,

결국 12원을 만드는 최종 경우의 수는:
2+2+2+2+4, 2+2+4+4, 4+4+4(2원과 4원으로 구해뒀던 8원을 만드는 경우의 수인 3가지)와
2+2+2+2+2+2(2원으로 12원을 만드는 경우의 수인 1가지)를 더한 4가지가 되어야 한다.

 

이전에 4원을 만드는 경우의 수를 구할 때도 먼저 2원을 사용했을 때 2+2라는 1가지가 카운트되어있다. 그 상태에서 4원짜리를 추가하려고 하면, 2+2로 만드는 경우(기존 값) + 4로 만드는 경우(새로 동전 사용: 4-4=0원 만드는 경우의 수)를 더한 2가지가 된다.

 

 

그래서 이걸 코드로 구현하면

  int n = Integer.parseInt(br.readLine()); //동전 종류 수

  int[] coins = new int[n];
  StringTokenizer st = new StringTokenizer(br.readLine());
  for(int j=0; j<n; j++) {
    coins[j] = Integer.parseInt(st.nextToken()); //오름차순 
  }

  int m = Integer.parseInt(br.readLine()); //만들어야하는 금액 

  int[] cnt = new int[m+1]; //각 금액별 경우의 수 
  cnt[0] = 1; //0원은 1가지 고정 

  //현재 금액을 만들기 위한 경우의 수는 (현재 금액 - 동전 액수)원을 만드는 경우의 수 + 기존 값
  for(int coin : coins) {
    for(int price=coin; price<=m; price++) {
      cnt[price] += cnt[price-coin];
    }  
  }

  System.out.println(cnt[m]);

주의할 점은 0원을 만들 수 있는 가짓수는 1개로 고정되기 때문에 이 부분을 먼저 처리해주어야한다는 점이다.

price를 coin으로 초깃값을 설정한 이유는 어차피 그 밑으로는 현재 동전을 가지고 금액을 만들 수 없기 때문이다.

 

나름대로 논리적으로 구체적으로 생각해봤는데 여전히 좀 애매모호한 부분이 있는 것 같긴 하다..