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

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

프로그래머스

 

처음부터 도저히 감이 안잡힌 문제라서 다른 블로그를 봤더니 대부분이 깊이 우선 탐색(dfs)으로 문제를 해결하는 걸 봤습니다. 깊이 우선 탐색에 대해서 잘 모르시는 분은 아래를 참고해주세요. (https://sookr5416.tistory.com/103)

[JAVA] 깊이 우선 탐색 DFS 개념과 작동 방식

class Solution {
    private int answer = Integer.MAX_VALUE;
    public int solution(int N, int number) {
 
        dfs(N, number, 0, 0);
        
        if (answer > 8) return -1; // 최소값이 8보다 크면 -1을 return
        return answer;
    }
    
    public void dfs(int N, int number, int idx, int sum) {
        if (idx > 8) return;
        if (sum == number) { // +, -, *, / 한 값이 number와 동일한 경우
            answer = Math.min(idx, answer);
        }
        
        int num = 0;
        for (int i=1; i<=8; i++) {
            num = 10 * num + N; // 5, 55, 555, ···
            dfs(N, number, idx + i, sum + num);
            dfs(N, number, idx + i, sum - num);
            dfs(N, number, idx + i, sum * num);
            dfs(N, number, idx + i, sum / num);
        }
    }
}