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

문제 설명

1. 숫자 N과 number이 주어진다.

2. number을 N을 사용해서 만들 수 있는 경우가 여러 가지 있는데, 이 중 최소횟수를 구한다.

3. 8회 초과이면 -1을 return한다.

풀이 과정

 1. DP문제인데 나는 DFS랑 최적해를 섞어서 푼것같다.... DP만으로 푸는 방법은 모르겠음......

 2. N을 통해 +-/*를 해서 구할 수 있는 모든 방법을 구한다.

 3. 위의 process를 전체 문자열의 길이만큼 진행하면 구할 수 있다.

 4. 그리고 N뿐만 아니라 NN NNN 이런것도 가능하다. 참고로 이경우 count는 당연히 하나 늘어날 것이다.

 5. 마지막으로 중요한게 8회 초과이면 -1을 리턴하도록 만들면 된다.

 

tip ) 그리고 시간복잡도를 조금이나마 줄이는 방법인데, 어차피 최소의 값을 return할 거면 변수 하나를 시작할 때 9로 세팅하고, number을 그 안에 구현하면 이를 해당 변수에 저장하며, 그보다 큰 값들은 답이 될 수 없으므로 걍 나가주면 될 것이다. 이렇게 하면 쓸데없이 뒤를 더 돌릴 필요가 없어서 시간을 아낄 수 있을 것이다.

코드

class Solution {
    public static int ans = 9;
    
    public int solution(int N, int number) {
        int answer = -1;
        
        dfs(N, 0, 0, number);
        
        if(ans<9) answer = ans;
        return answer;
    }
    public static void dfs(int N, int cnt, int nowNum, int number){
        if(cnt >= ans) return;
        if(nowNum == number){
            ans = cnt;
            return;
        }
        
        int cal = N;
    	for(int i = 0; i<8-cnt; i++ ) {
            dfs(N, cnt+1+i, nowNum+cal, number);
            dfs(N, cnt+1+i, nowNum-cal, number);
            dfs(N, cnt+1+i, nowNum*cal, number);
            dfs(N, cnt+1+i, nowNum/cal, number);
        	
        	cal = (cal*10)+N;
    	}
    }
}