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

Level3

풀이

• 5를 예시로 들어보자.

1. 5를 1번 사용
   • 5
2. 5를 2번 사용
   • 55, (5 * 5), (5 / 5), (5 - 5), (5 + 5)
     • 55, 25, 1, 0, 10
3. 5를 3번 사용
   • 555, (55 * 5), (55 / 5), (55 - 5), (55 + 5)
   • ((5 5) 5), ((5 5) / 5), ((5 5) + 5), ((5 * 5) -5)
   • ((5 / 5) * 5), ((5 / 5) / 5), ((5 / 5) + 5), ((5 / 5) -5)
   • ((5 + 5) * 5), ((5 + 5) / 5), ((5 + 5) + 5), ((5 + 5) -5)
   • ((5 - 5) * 5), ((5 - 5) / 5), ((5 - 5) + 5), ((5 - 5) -5)

11, 22등의 N이 연달아서 나오는 경우도 고려하여야 한다.

코드

class Solution {
    int answer = - 1;
    
    public int solution(int N, int number) {

        dfs(0, 0, number, N);
        return answer;
    }
    public void dfs(int cnt, int now, int number, int N) {
        if(cnt > 8)
            return;
        
        if(now == number) { 
            if(answer == -1 || answer > cnt) 
                answer = cnt;
            return;
        }
        
        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;
        }
    }
}