Programmers 12907: 거스름돈

dp[n]: n원을 낼 수 있는 가짓수로 정의한다.

class Solution {
	public int solution(int n, int[] money) {
		int dp[] = new int[n + 1];
		dp[0] = 1;

		for (int coin : money) {
			for (int i = 1; i <= n; i++) {
				if (i - coin >= 0) {
					dp[i] += dp[i - coin];
				}
			}
		}

		return dp[n];
	}
}

 

 

왜 2중for문의 안과 밖이 바뀌면 중복된 값, 예를 들어 [10, 20, 10]과 [10, 10, 20]을 다른 경우로 체크해서 더 많은 값이 나온다.