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

[문제]

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

알고리즘 연습 - N으로 표현 | 프로그래머스

[풀이방법]

 

이 문제가 DP로 되어있던데 DP로는 어떻게 푸는 지 모르겠네요.. 

 

저는 DFS로 사칙연산을 하고 그 값과 number를 비교해서 같은 경우에 최소값을 비교해줬습니다. 

 

문제에서 잘 못 본 부분이 

• 최솟값이 8보다 크면 -1을 return 합니다.

여기에서 8보다 클 때 answer를 -1로 만들고 리턴합니다. (저는 여기서 같아질 때 -1로 해서 답이 이상하게 나왔습니다.)

 

다른 문제와는 다르게 answer의 초기값을 -1로 했습니다. 원래는 최소값이 나올 때 초기값으로 정수의 최대값을 주었는데 그렇게 하니까 최소값 비교에서 answer이 cnt보다 작은 값으로 간주하더라구요 (cnt가 dfs에서 크게 증가합니다)

 

그래서 answer = -1로 두고 number == prev(연산 결과값) 일 때,

answer == -1 || answer > cnt 라면 answer = cnt 

 

그리고 사칙연산을 진행해야 합니다. 테스트 케이스 예제를 보면 

[ N = 5 / number = 12 ]

 

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

 

N을 55로 만들어서 연산을 진행합니다. 이 부분을 처리하기 위해 사칙연산을 진행한 후에

N과 같은 값의 temp_N을 생성해서 temp_N *N + N으로 N의 값을 변경해줍니다. 

당연히 N으로 나누는 게 아니라 temp_N으로 나누어야 합니다. 

 

---

 

 

class Solution {
    static int answer =-1;
    
    public int solution(int N, int number) {
        
        dfs(N, number, 0,0);
        return answer;
    }
    static void dfs(int N, int number , int cnt, int prev) {
        //N의 카운트를 늘려가며 dfs 로 수행한다. 
        //그 값을 저장하고 그 값이 number와 동일한지 확인한다. 
        int temp_N = N;
        if (cnt > 8) {
            answer = -1;
            return;
        }
        
        if (number == prev ) {
            if (answer == -1 || answer > cnt)
                answer = cnt;
            return;
        }
        
        for (int i = 0; i < 8-cnt; i++) {
            dfs(N, number, cnt+i+1, prev-temp_N);
            dfs(N, number, cnt+i+1, prev+temp_N);
            dfs(N, number, cnt+i+1, prev*temp_N);
            dfs(N, number, cnt+i+1, prev/temp_N);
            
            temp_N =  increaseNumber(temp_N, N);
        }
    }
    static int increaseNumber(int value, int N) {
        return value * 10 + N;
    }
}