프로그래머스 N으로표현 - DP

문제링크

문제풀이 흐름

문제를 보고 어떻게 푸는지 감이 안왔다. DP문제라는 것을 알고 봐서 DP[목표숫자] = 최소 숫자 로 구성되진 않을까 하고 끼워맞춰 보려했지만 실패했다. 결국 답안지를 봤다.

number를 만들기 위해 필요한 개수를 바로 계산할 수 없어보이므로, 반대로

N을 1개만 사용해서 얻을 수 있는 숫자를 구해보고, N을 2개만 사용해서 얻을 수 있는 결과를 구해봤다.
N을 3개... 이렇게 결과를 구해보면

N을 k개 사용해서 만들 수 있는 결과를 구하려면 기존의 결과중 임의의 두개의 집합에서 하나씩 꺼내올 경우 결과를 구할 수 있다.

이것이 핵심아이디어이다. 문제풀이 흐름을 정리하자면
1. N이 1개있을때 구할 수 있는 집합을 구해서 저장한다.
2. N이 2일때 구할 수 있는 집합을 N이 1개일때 구한 집합으로 구한다.
...

3. N이 8개일대 구할 수 있는 집합을 N이 1개~7개일때 구한 집합으로 구한다.
4. 구하는 도중 집합에 목표 number가 포함되어 있다면 k를 리턴한다.

이런식으로 기존의 계산을 통해 최종 값을 구할 수 있다.

import java.util.*;


class Solution {
    public int solution(int N, int number) {
        
        ArrayList<HashSet<Integer>> dp = new ArrayList<HashSet<Integer>>();
        
        for(int i=0;i<9;i++){
            dp.add(new HashSet<Integer>());
        }
        
        dp.get(1).add(N);
        
        if(N==number){
            return 1;
        }
        
        // i개로 만들 수 있는 숫자 집합 구하기
        for(int i=2;i<=8;i++){
            
            int num = 0;
            for(int p=0;p<i;p++){
                num *= 10;
                num += N;
            }
            
            dp.get(i).add(num);
            
            for(int j=1;j<i;j++){
                int k = i-j;
                
                for(int num1 : dp.get(j)){
                    for(int num2 : dp.get(k)){
                        
                        dp.get(i).add(num1+num2);
                        dp.get(i).add(num1-num2);
                        dp.get(i).add(num1*num2);
                        
                        if(num2 != 0){
                            dp.get(i).add(num1/num2);
                        }
                    }
                }
            }
            
            if(dp.get(i).contains(number)){
                return i;
            }
        }
        
        return -1;
    }
}

놓친점 1

DP에 대한 감이 전체적으로 부족했다. 해당 문제에서는
dp[N의 개수] = {만들 수 있는 숫자 집합} 을 구했어야 했다.
그리고 집합안에 정답이 포함되면 종료하는 방식으로 풀었어야 했다.

여기서는 dp[만들 수 있는숫자] = N의 최소 개수

로 계속접근하려면 답이 나오지 않는다. 이렇게 구체화할 수 있는 방법이 없는지 바꿔서도 생각해봐야겠다.