N으로 표현(동적계획법(Dynamic Programming))

문제

코드

class Solution {
    int answer=Integer.MAX_VALUE;
    public int solution(int N, int number) {
        dfs(0,0,N,number);
        if(answer==Integer.MAX_VALUE) return -1;
        return answer;
    }
    public void dfs(int count,int value,int N,int number){
        if(count>8) return;
        if(value==number){
            answer=Math.min(answer,count);
            return;
        }
        int newN=0;
        for(int i=0;i<5;i++){
            newN=newN*10+N;
            dfs(count+1+i,value+newN,N,number);
            dfs(count+1+i,value-newN,N,number);
            dfs(count+1+i,value*newN,N,number);
            dfs(count+1+i,value/newN,N,number);
        }
    }
}

풀이

(1) dfs 알고리즘을 사용한다. 기본 원칙은 0부터 시작하여 N으로 만들 수 있는 모든 경우의 수를 탐색하는 것이다. 이 때, N을 사용한 횟수가 8회를 넘어가면 탐색을 종료하고, 그 전에 만들고자하는 수를 탐색했다면 그 횟수를 새로 갱신하는 것이다.(최소 횟수가 되도록)
(2) 만약 N이 5이고 0에서부터 dfs를 시작했을 때, 만들 수 있는 수의 경우의 수는 4가지이다. 5을 더하거나, 빼거나, 곱하거나, 나누거나. 이렇게 4가지 방법으로 dfs 함수를 재귀호출 시켜준다. 이 때, 5 뿐만 아니라 55,555,5555를 연산해 줄 수 있기 때문에, for문으로 이들을 연산한 탐색도 재귀호출 시켜준다.(i<5인 이유는 number의 최댓값이 32000이기 때문에, NNNNNN부터는 계산할 필요가 없다.)
(3) 위 과정을 반복하며 찾고자 하는 수가 8번 이하의 탐색으로 나오면, 최솟값을 갱신하여 준다,

결과

문제 카테고리가 DP이기도 하고, 문제를 보니 DP로 풀 수 있을 것 같아서 처음에는 dp배열을 돌면서 만들 수 있는 숫자를 만나면 거기서 사칙연산 4가지를 해서 배열을 갱신하도록 하는 방식으로 풀었는데, 테스트 케이스 4개정도를 통과하지 못했다.
어떤 방법으로 해야할 지 감이 잡히지 않아, 게시판을 봤더니 dp문제보다는 완전탐색 문제에 가깝다고 한다. 그냥 모든 경우의수를 다 보는게 맞다고 한다. 문제에서도 N이 나온횟수가 8을 넘으면 -1을 출력하라고 했기 때문에, 아마 dfs 알고리즘으로 완전탐색 하여도 스택 오버플로우가 나지 않을 것으로 예상하여 dfs로 해결하였다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges