[문제풀이] 거스름돈

업데이트:

문제 링크 : 거스름돈

풀이 시간 : 측정 불가

1. 문제 풀이

동전을 사용해서 만들 수 있는 n을 만들 수 있는 경우의 수 찾는 문제

여러 동전의 종류가 있고 동전의 수는 무한하다는 가정

동전의 종류 i개로 j(0 ~ n)을 만들 수 있는 경우를 구하는 방법

(i,j) = (i-1,j) + (i,j-money[i])를 이용하여 풀이

2. 소스 코드

    public int solution(int n, int[] money) {
		long[] v = new long[n + 1];
		v[0] = 1;
		for (int i = 0; i < money.length; i++) {
			// 동전의 종류 i 개로 j를 만들 수 있는 경우
			for (int j = money[i]; j <= n; j++) {
				v[j] += v[j - money[i]];
			}
		}
		return (int) (v[n] % 1000000007);
	}

3. 후기

처음에는 완전 탐색으로 구현하였지만 효율성에서 실패하였습니다.

DP를 이용해서 풀려고 했지만 한번에 모든 종류를 사용하려고 해서 못 풀었습니다.(시간 측정 불가 이유)

i개씩 먼저 구한다는 힌트를 보고 해결하였습니다.

참고