빠에야는 개발중

거스름돈 본문

공부/알고리즘 문제

거스름돈

빠에야좋아 2018. 3. 15. 14:33

물건 값보다 많은 돈을 낼 경우 거스름돈을 돌려주게 됩니다. 거스름돈은 한 금액의 돈으로 줄 수도 있지만, 여러 금액의 동전을 섞어 거슬러 줄 수 있습니다.

거스름돈이 N원일 때, 1원, 2원, 5원 동전이 있다면 몇 가지 방법으로 돈을 거슬러 줄 수 있을까요? change 함수를 통해 경우의 수를 반환해주는 함수를 만들어 보세요. K에는 사용할 수 있는 동전의 종류가 들어 있습니다.

예를 들어, N = 5이고 K = [1, 2, 5]이면 1원, 2원, 5원 동전을 가지고 5원을 맞추는 경우의 수를 찾으면 됩니다.

  • 1원 5개
  • 1원 3개, 2원 1개
  • 1원 1개, 2원 2개
  • 5원 1개

이렇게 총 4가지 경우가 있으면, 4를 리턴해 주면 됩니다.


각각의 순서가 의미가 없기 때문에 bfs로는 풀 수 없을 것 같았고 dp를 사용해야할 것 같은데 점화식을 어떻게 잡아야할지 감이 잘 오지 않았다. 결국 값 자체에 집중을 하면 된다는 걸 알았고 검색을 동원하여 풀었다. 복잡한 조건에서 값들을 잘 조정하는 것이 아직 미숙한 것 같다.


자세한 방법은 어떤 코인의 방법은 (금액 - 코인)한 금액을 그 전 코인의 방법으로 구한 값을 더해주는 것이다. 예를들어 5라는 숫자를 1, 2로 구하고 싶다면 방법은

1 1 1 1

2 1 1

2 2 1

이렇게 세가지인데 이는 각각 (5-0), (5-2), (5-4)를 1로 구한 방법의 가지수와 동일하다.

한가지 주의할 점은 첫줄을 초기화할 때 나누어 떨어지지 않아 구할 수 없는 경우의 수도 있다는 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Change {
 
    public int change(int total, int[] coins) {
        int answer = 0;
        int[][] d = new int[coins.length][total + 1];
 
        for (int i = 0; i < coins.length; i++) {
            for (int j = 0; j < total + 1; j++) {
                if (i == 0) {
                    if(j%coins[i] == 0) {
                        d[i][j] = 1;
                    } else
                        d[i][j] = 0;
                    
                } else {
                    d[i][j] = d[i - 1][j];
                    for (int k = 1; j >= coins[i] * k; k++) {
                        d[i][j] += d[i - 1][j - (coins[i] * k)];
                    }
                }
            }
 
        }
        answer = d[d.length - 1][total];
        return answer;
    }
 
    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        Change c = new Change();
        int[] coins = { 1, 2, 5 };
        System.out.println(c.change(5, coins));
    }
}
 
cs


'공부 > 알고리즘 문제' 카테고리의 다른 글

Jumping on the Clouds  (0) 2019.03.29
단순 연결리스트 역순으로 뒤집기  (0) 2018.04.02
3xn 타일링  (0) 2018.03.15
과자 많이 먹기  (0) 2018.03.15
줄 서는 방법  (0) 2018.03.14
'공부/알고리즘 문제' Related Articles more
Comments