[프로그래머스 / Level3] N으로 표현 (Java)

다이나믹 프로그래밍으로 풀어야 하는데 DFS로 풀이한 것 같다.
다이나믹 프로그래밍을 더 연습하자.

문제 보기

사용한 것

• N을 8번 이하 사용하여 목표 값을 구할 수 있는지 판별하기 위한 DFS

풀이 방법

• DFS를 진행하면서 더하거나, 빼거나, 나누거나, 곱한다.
• 사칙연산을 사용하지 않고 붙여서 사용하는 경우도 생각한다. (5 두번하면 55)
• N의 사용 횟수가 8이 넘어가면 return 한다.
• DFS를 진행하는 도중 목표 값이 되면 N을 더 적게 사용한 것을 answer에 갱신한다.
• answer를 반환한다.

코드

class Solution {

    private int n;
    private int target;
    private int answer = Integer.MAX_VALUE;

    public int solution(int N, int number) {
        n = N;
        target = number;
        
        dfs(0, 0);

        return answer == Integer.MAX_VALUE ? -1 : answer;
    }

    private void dfs(int depth, int num) {
        if (depth > 8) {
            return;
        }

        if (num == target) {
            answer = Math.min(answer, depth);
            return;
        }

        int tempN = n;
        for (int i = 1; i <= 8 - depth; i++) {
            int nextDepth = depth + i;
            dfs(nextDepth, num + tempN);
            dfs(nextDepth, num - tempN);
            dfs(nextDepth, num / tempN);
            dfs(nextDepth, num * tempN);

            tempN = tempN * 10 + n;
        }
    }
}