프로그래머스_배달_자바

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

코딩테스트 연습

다음 문제는 다이내믹 프로그래밍을 대표하는 문제이다. 

다이내믹 프로그래밍이랑 하나의 문제를 더 작은 부분 문제로 나눠서 푸는 것이다.

여기서 조건은 나눠진 부분 문제들이 중복해서 나타나는 것이다.

최적 부분 구조라고 한다.

다음 문제를 보면 n 원을 만들기 위해서 1, 2, 3, ~~ n-1 원에서 구했던 값들을 이용하여 푼다.

예시를 들어보자 

예를 들어 동전 1, 2, 5 가 있고 5원을 만들어야 한다.

그럼 일단 1원으로 5원을 만드는 경우를 나타내 보자 (1, 2, 5 간에 순서는 상관없다.)

 

원   / 0 1  2  3  4  5

개수/ 1 1  1  1  1  1 

위에서 살펴보면 0원을 만들 수 있는 경우는 1가지이다.(동전을 쓰지 않으면 만들 수 있기 때문이다.)

1원을 만들기 위해서는 0 원을 만들 수 있는 가짓수에서 1원을 더 해주면 된다.

2원을 만들기 위해서는 1원을 만들 수 있는 가짓수에서 1원을 더 해주면 된다.

이 말을 풀이하자면 1원을 만들 수 있는 경우가 1가지라 하자 2원을 만들기 위해서는 1원에서 1 원한 개를

추가해주면 된다. 가짓수는 변하지 않는다. 예를 들어 높이가 5m인 탑이 있다고 하자 탑을 더 쌓아 높이를

7m로 증가시킨다 해도 탑의 개수는 변하지 않는 것처럼 말이다.

 

이제 2원도 사용해보자 

현재는 이러한 상태이다.   (1)

원   / 0 1  2  3  4  5

개수/ 1 1  1  1  1  1 

 

현재 상태에서 2원을 사용한다면 결과는 다음과 같이 된다.  (2)

원   / 0 1  2  3  4  5

개수/ 1 1  2  2  3  3

 

0, 1원일 때는 2원을 사용할 수가 없다. 2원을 넘어가기 때문이다. (1)에서 구해준값과 같다.

2원 들어 보자 2원을 만들 수있는 방법은 0원을 만들수있는 방법에서 2원을 더해주는것이다.(1가지) 이때 (1) 에서 구해준것과 더해준다. 

3원을 만들어보자 3원을 만들 수있는 방법은 1원을 만들수 있는 방법에서 2원을더해주는것이다.(1가지) 이때 (1) 에서 구해준것과 더해준다.

4원을 만들어보자 4원을 만들수있는 방법은 2원을 만들수 있는 방법에서 2원을 더해주는 것이다.(2가지) 이때 (1)에서 구해준 것과 더해준다.

 

위와 같은 방식으로 문제를 해결해 나가면 된다.

다음은 전체 코드이다.

class Solution {
    public static int solution(int n, int[] money) {
        int answer = 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int i = 0; i < money.length; i++) {
        	for(int j = money[i]; j <= n; j++) {
        		dp[j] += dp[j - money[i]];
        	}
        }
        return dp[n];
    }     
}