[프로그래머스 - Java] N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

풀이

 

프로그래머스에는 이 문제가 DP로 분류되어 있지만 왜 그런지 이해가 가지 않습니다...

DP로 대체 어떻게 푸는 걸까 하고 삽질하다가 검색해보니 다들 DFS로 풀어서 저도 DFS로 풀이하였습니다!

최대 8개의 N으로 number를 나타내야 하므로 걸리는 시간이 그리 크지 않은 선에서 해결 가능합니다.

 

이 문제에서 중요한 것은 NN....N을 고려해서 처리하는 것입니다.

따라서 dfs호출시에 재귀로 사칙연산만 수행하는게 아니라 <기존값 + NN...N>같은 경우도 풀이가능하도록 코드를 구현해야 합니다.

저는 이부분이 너무 어려웠어요ㅠㅠㅠ

 

class Solution {
    
    int answer = -1;

    public int solution(int N, int number) {
        if(N==number)
            return 1;
        
        dfs(0, 0, number, N);        
        return answer;
    }

    private void dfs(int cnt, int now, int number, int N) {
        if (cnt > 8) 
            return ;
        
        //number 만들었음!
        if (now == number) {
            if(answer == -1 || answer > cnt)
                answer = cnt;
            return ;
        }

        //사칙연산 뿐만 아니라 NN...N도 처리해야함!!!
        int nn = N;
        for (int i = 0; i < 8 - cnt; i++) {
            dfs(cnt+i+1, now + nn, number, N);
            dfs(cnt+i+1, now - nn, number, N);
            dfs(cnt+i+1, now / nn, number, N);
            dfs(cnt+i+1, now * nn, number, N);

            nn = nn * 10 + N;
        }
    }
}