DP를 이용한 경우의 수 찾기

문제

여러가지 지폐의 종류로 원하는 액수를 가저갈수 있는 모든 경우의 수를 구하라.

 

예를들어 $50, $20, $10 3가지의 지폐종류가 있고 총 50 달러를 가저가려할때 가질수 있는 모든 경우의 수인 4를 구해 반환해야 한다.

• $50 * 1
• $20 * 2, $10 * 1
• $20 * 1, $10 * 3
• $10 * 5

 

입력

int 타입의 자연수 int target

int 타입의 요소를 갖는 배열 int[] type

 

 

출력

long 타입의 모든 경우의 수 

 

 

 

풀이

재귀

class Solution {
    public long ocean(int target, int[] type) {

    int[] newType = IntStream.of(type).boxed().sorted(Collections.reverseOrder()).mapToInt(a->a).toArray();

    return recursion(newType,target,0);
    }

    long recursion(int[] newType, int target, long count){

        if(target==0) return ++count;
        if(newType.length==0) return count;
        if(newType[newType.length-1]>target) return count;

        int numberOfCoins = target/newType[0];

        while(numberOfCoins>=0){
            int leftTarget = target - newType[0] * numberOfCoins;

            count = recursion(Arrays.copyOfRange(newType,1,newType.length), leftTarget, count);
            numberOfCoins--;
        }
        return count;
    }
}

처음 문제를 풀때 재귀를 활용하여 문제를 풀었는데 계속해서 시간초과로 인해 실패하였다... 이후 동적계획법에 대해 알게되어 이것을 이용하였더니 오류없이 통과할 수 있었다.

 

 

DP - Bottom up

class Solution {
    public long ocean(int target, int[] type) {
        long[] table = new long[target + 1];
        table[0] = 1;

        for(int i = 0; i < type.length; i++) {
            for(int j = 1; j <= target; j++)

                if(type[i] <= j)
                    table[j] += table[j-type[i]];

        }

        return table[target];
    }
}

동적계획법 중 Bottom_up을 이용하였으며 그에 관한 포스트는 아래 링크에...

https://mason-lee.tistory.com/79

 

 

마무리 (수도 코드 작성 팁)

여지껏 수도코드를 작성안하고 코딩테스트를 풀어 왔었는데 막상 수도코드를 작성하려고 하니 막막했다.

심지어 수도코드를 작성하고 코드의 풀이가 더 뒤죽박죽되며 복잡해지고 결과가 원하는대로 나오지 않는 등 많은 문제가 생기게 되어 수도 코드 작성시 몇가지 룰을 정하게 되었다.

 

1. 모든 테스트 코드의 경우의 수를 담는 입력값을 만들고 (혹은 그런 테스트 코드를 사용) 그에 맞는 결과값을 일단 도출 
2. 입력값과 출력값의 상관관계 혹은 해당 출력값이 나오게된 원리, 구조, 법칙등을 파악하고 어떠한 순서와 규칙이 숨어 있는지 파악
3. 파악한 규칙을 토대로 수도코드를 작성