[Lv3] 거스름돈

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.

예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.

• 1원을 5개 사용해서 거슬러 준다.
• 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
• 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
• 5원을 1개 사용해서 거슬러 준다.

거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• n은 100,000 이하의 자연수입니다.
• 화폐 단위는 100종류 이하입니다.
• 모든 화폐는 무한하게 있다고 가정합니다.
• 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요.

---

입출력 예

n	money	result
5	[1,2,5]	4

 

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

 

 

---

 

동전(화폐)는 같은 종류는 무한정 쓸 수 있음.

어떤 화폐가 주어지는지는 문제마다 변함.

 

화폐 종류는 100종류까지 나올 수 있고, 화폐의 사용 가능 수는 무제한이라 재귀함수로 돌리면 시간초과/메모리초과가 날겁니다.

 

수학적으로 규칙성을 찾아야겠죠..

 

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2(1,2)	1	2	2	3	3	4	4	5	5	6
3(1,2,3)	1	2	3	4	5	7	8	10	12	14
4(1,2,3,4)	1	2	3	5	6	9	11	15	18	23
5(1,2,3,4,5)	1	2	3	5	7	10	13	18	23	30

 

가로는 총 금액, 세로는 사용할 동전입니다.

 

1원만으로는 각 금액에 대해 1원짜리*n 동전박치기 한가지 경우씩 밖에 못 만들겠죠.

 

2원이 추가되면, 2원때부터 변화를 맞이합니다.(1,1/2)

 

3원이 추가되도, 2원까지는 3원을 못 쓰니 여전하지만, 3원때부터 변화를 맞이합니다.(1,1,1/2,1/3)

 

윗 행 그대로 번호가 내려오지 않고 변화가 시작되는 지점이 금액이 딱 자기자신일 때입니다.(3원이면 3번째부터)

 

노랗게 표시된 부분은 이렇게 구해집니다.

 

 

녹색부분부터 그 오른쪽은 전부 자기위의수+n칸왼쪽수(n은 이번에 추가된 동전단위) 입니다.

 

다른 예도 그런지 봅시다.

 

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
3	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1
8(3,8)	0	0	1	0	0	1	0	1	1	0	1	1	0	1	1	1	1	1	1	1	1
9(3,8,9)	0	0	1	0	0	1	0	1	2	0	1	2	0	1	2	1	2	3	1	2	3

 

3원만으로는 3의 배수만 표현 가능합니다. (맨 처음의 예제는 1이었으니 전부 가능했지만)

3,8원 행에서는 역시 8번째부터 위의 숫자대로 넘어오지 않고 변화가 생겼습니다.

3,8,9원 행에서도 9번째부터 변화가 생겼습니다.

 

역시 바로 다음칸부터 위의수+n칸이전수의 규칙을 보여줍니다.

 

 

 

정리해봅시다.

 

동전은 아마 중복이 없는 다른 종류로 주어질 것.

이를 오름차순으로 정렬해 둠.

 

첫 행은 최소동전의 배수(%=0)만 1. 나머진 0.

 

그 다음 행들은 0~자기자신 전까진 그대로 위의 수 복사.

자기자신번째는 위의 수+1.

자기자신번째 이후는 위의 수+n칸이전수.

 

 

public int solution(int n, int[] money) {
    Arrays.sort(money);
    int[][] answer = new int[money.length][n];
    for(int i=0;i<n;i++) if((i+1)%money[0]==0) answer[0][i]=1;
    for(int i=1;i<money.length;i++) {
        int now = money[i];
        for(int j=0;j<n;j++) {
            if(j==now-1) answer[i][j] = (answer[i-1][j]+1)%1000000007;
            else if(j<now-1) answer[i][j] = answer[i-1][j];
            else {
                answer[i][j] = (answer[i-1][j] + answer[i][j-now])%1000000007;
            }
        }
    }
    return answer[money.length-1][n-1];
}

코드로 표현하면 이렇습니다만, 이대로는 효율성에서 2군데 통과하지 못합니다.

 

시간을 더 줄여봅시다.

 

2차원 배열을 1차원으로 줄이는 방법을 생각해봅니다.

 

 

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2(1,2)	1	2	2	3	3	4	4	5	5	6
3(1,2,3)	1	2	3	4	5	7	8	10	12	14
4(1,2,3,4)	1	2	3	5	6	9	11	15	18	23
5(1,2,3,4,5)	1	2	3	5	7	10	13	18	23	30

노란칸은 위의 수에 1을 더하게 되는 것이고, 녹색 이후부터는 위의 수+n칸이전수 입니다.

 

우리는 마지막행 마지막열만 필요하므로, 누적값으로 압축시켜봅시다.

 

01 01 01 01 01 01 01 01 01

01 02 02 03 03 04 04 05 05 에서,

위의 행이 기준이되고.(어차피 위의수에 1을 더하든 n칸이전수를 더하든 위의수에 누적되니까)

노란칸번째는 1만 더하고, 녹색칸부터는 n칸이전수를 더합니다.

01 02 02 03 03 04 04 05 05

 

이제 다음으로 넘어오면,

 

01 02 02 03 03 04 04 05 05

01 02 03 04 05 07 08 10 12에서, 01 02 03 04 05 07 08 10 12가 되고,

 

01 02 03 04 05 07 08 10 12

01 02 03 05 06 09 11 15 18에서, 01 02 03 05 06 09 11 15 18이 되고,

 

01 02 03 05 06 09 11 15 18

01 02 03 05 07 10 13 18 23에서, 01 02 03 05 07 10 13 18 23이 됩니다.

 

이런식으로 한 행에 마지막행을 표현할 수 있습니다.

 

public int solution(int n, int[] money) {
    Arrays.sort(money);
    int[] answer = new int[n];
    for(int i=0;i<n;i++) if((i+1)%money[0]==0) answer[i]=1;
    for(int i=1;i<money.length;i++) {
        int now = money[i];
        for(int j=now-1;j<n;j++) {
            if(j==now-1) answer[j]=(answer[j]+1)%1000000007;
            else if(j>now-1) {
                answer[j] = (answer[j]+answer[j-now])%1000000007;
            }
        }
    }
    return answer[n-1];
}

당연하지만 j는 now-1부터 하면 됩니다.

 

이제 시간이 단축되어 통과됩니다.