[프로그래머스] Level 3 N으로 표현 (JAVA)

문제

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

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

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

---

풀이

도저히 아이디어가 떠오르지 않아서 검색해서 풀었다. DP 카테고리에 있는 문제지만 내가 생각했던 것도 DFS였기 때문에 DFS를 구현한 코드를 보고 이해해보았다. DP 풀이는 이해하는데 시간이 좀 걸릴 것 같다.

1. 여태까지 연산한 횟수인 count와 이전까지의 연산 결괏값 prev을 파라미터로 넘기며 DFS를 수행한다.
2. 종료 조건은 2가지이다.
   • count가 8을 초과한 경우 answer는 -1이다.
   • count가 8 이하일 때 target 수가 만들어진 경우 answer를 최솟값으로 갱신한다.
3. 각 dfs()마다 한 자리씩 늘려가며 네 개의 사칙 연산을 추가로 하도록 재귀 호출한다.

---

코드

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 count, int prev) {
        if (count > 8) {
            answer = -1;
            return;
        }

        if (prev == target) {
            answer = Math.min(answer, count);
            return;
        }

        int tempN = n;
        for (int i = 0; i < 8 - count; i++) {
            int newCount = count + i + 1;
            dfs(newCount, prev + tempN);
            dfs(newCount, prev - tempN);
            dfs(newCount, prev / tempN);
            dfs(newCount, prev * tempN);

            tempN = tempN * 10 + n;
        }
    }
}

---

참고

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