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

문제

 

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

 

 

 

---

풀이

 

동적계획법(Dynamic Programming) 카테고리 문제였지만 숫자가 크지 않아서 경우를 백트래킹으로 전부 탐색 해볼 수 있는 문제였다. 

 

백트래킹 풀이

  ☞ 제한 사항에 최솟값이 8보다 크면 -1을 return한다는 점을 이용해서 N을 최대로 사용할 수 있는 횟수는 8회이다.

  ☞ 각 사칙연산을 수행 후 (N x 10 + 1)을 해서 N의 자릿수를 늘려서도 탐색한다.

 

public class Solution {
    private int N;
    private int number;
    private int answer = 9;

    private void dfs(int cnt, int prev) {
        if(prev == number) {
            answer = Math.min(answer, cnt);
        }
        int now = N;
        for(int i=0; i<8-cnt; i++) {
            int next = cnt + i + 1;

            dfs(next, prev + now);
            dfs(next, prev - now);
            dfs(next, prev * now);
            dfs(next, prev / now);

            now = now * 10 + N;
        }
    }

    public int solution(int N, int number) {
        this.N = N;
        this.number = number;

        dfs(0, 0);

        return answer == 9 ? -1 : answer;
    }
}

 

 

동적 계획법 풀이

  ☞ 핵심은 N_m일 때 N_(m-1), N_(m-2), N_(m-3), ··· ··· , N₂, N₁의 경우의 수 조합이다.

  ☞ 여기서 N_m은 N이 m개 사용되었을 때이다.

 

예를 들어 N = 5 일 때,

 

m = 1 이면

5

 

m = 2 이면

55,
5 + 5, 5 - 5, 5 × 5, 5 ÷ 5

 

m = 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

 

위 의 규칙을 이용하면, N 사용 횟수의 최소값을 알 수 있다.

 

import java.util.*;

public class Solution {

    public int solution(int N, int number) {
        if(N == number) return 1;

        List<Set<Integer>> dp = new ArrayList<>();
        int answer = -1;
        int unit = N;

        for(int i=0; i<8; i++) {
            Set<Integer> set = new HashSet<>();
            set.add(unit);
            dp.add(set);

            unit = unit * 10 + N;
        }
        for(int i=1; i<8; i++) {
            for(int j=0; j<i; j++) {
                for(int x : dp.get(j)) {
                    for(int y : dp.get(i-j-1)) {
                        dp.get(i).add(x + y);
                        dp.get(i).add(x - y);
                        dp.get(i).add(x * y);
                        if(y != 0) dp.get(i).add(x / y);
                    }
                }
            }
            if(dp.get(i).contains(number)) {
                answer = i + 1;
                break;
            }
        }

        return answer;
    }
}