[프로그래머스 Level3]DP:N으로 표현-JAVA (자바)

문제 링크

성능 요약

메모리: 96.6 MB, 시간: 5.83 ms

구분

코딩테스트 연습 > 동적계획법（Dynamic Programming）

문제 설명

아래와 같이 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 합니다.

입출력 예

Nnumberreturn

5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

풀이

• 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)
   •  

1	2	3
[  5  ]	[  5 * 5  ]    [  5 / 5  ]    [  5 - 5  ]    [  5 / 5  ]    [  55  ]	[  5 + (5 + 5)  ]   [  5 * (5 + 5)  ]   [  5 / (5 + 5)  ]   [  5 - (5 + 5)  ]   [  ...  ]   [  555  ]

 

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

코드

class Solution {
    int answer = -1;  // 초기값은 -1로 설정

    public int solution(int N, int number) {
        dfs(0, 0, number, N);  // DFS 탐색 시작
        return answer;  // 목표값을 만들 수 있는 최소 횟수 반환
    }

    public void dfs(int cnt, int now, int number, int N) {
        if (cnt > 8)  // 최대 8번까지만 연산을 수행 (문제 조건)
            return;

        if (now == number) {  // 목표값을 찾았다면
            if (answer == -1 || answer > cnt)  // 처음 목표값을 찾거나, 더 적은 횟수로 찾았다면
                answer = cnt;  // 최소 횟수 갱신
            return;
        }

        int nn = N;  // nn은 N의 값을 점차적으로 확장하면서 계산에 사용
        for (int i = 0; i < 8 - cnt; i++) {  // 남은 횟수가 8을 넘지 않도록 반복
            // 연산을 4가지 경우 (더하기, 빼기, 곱하기, 나누기)로 시도
            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;  // N을 10의 자릿수로 확장하여 연산에 사용
        }
    }
}