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

문제

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

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

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

제한사항

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

입출력 예

입출력 예 설명

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

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

출처

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

동적 프로그래밍

동적 프로그래밍 문제는 큰 문제를 작은 문제를 사용해 풀어낼 수 있고, 그 작은 문제의 해가 항상 같다면 해결할 수 있다. 요점은 큰 문제를 작은 문제로 쪼개는 것이다. 그리고 그것을 점화식으로 표현할 수 있다면 거의 다 푼 것이나 마찬가지이다.

원리

위 문제에서 큰 문제란 N으로 number를 어떻게 표현하는가? 이고, 작은 문제란 N으로 number보다 작은 자연수를 어떻게 표현하는가? 이다. 그리고 number는 number보다 작은 자연수의 조합으로 표현할 수 있다.

예를 들어, number = A * B 일 경우, A를 NN, B를 N+N으로 표현 가능하다면 아래 식처럼 number 도 A와 B가 조합된 N으로 표현 가능하다.

number = A * B = (NN) * (N+N) = NN * N + NN * N 

그렇다면 우리가 해야 할 것은 N을 1번 사용했을 때 표현할 수 있는 수부터 시작해 N을 임의의 횟수만큼 사용했을 때 표현할 수 있는 수 까지 위의 원리를 이용해 구하고, 그 중에 number가 있는지 확인하는 것이다.

다시 예를들어, N = 5 인 경우 N을 i번 사용하여 만들 수 있는 수들을 나열해보자.

 

i=1 : 5
i=2 : 55, 5+5, 5-5, 5*5, 5/5
i=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, ....

 

 

위의 식에서 알 수 있듯, i=3의 수들은 i=2와 i=1의 수들의 조합(사칙연산)으로 만들 수 있다.

위의 원리를 각 횟수(N을 사용하는 횟수)에 대해 일반화된 식으로 바꾸어보자.

N을 i번 사용해서 만들 수 있는 수의 조합을 SET i 라고 하자. 여기서 위의 원리를 적용하면 각 SET i를 점화식으로 표현할 수 있다.

$$ SET (i) = SET(1)\times\ SET(i-1)\\ \cup SET(2)\times \ SET(i-2)\\ \cup ... \\ \cup SET(i-1)\times SET(1) $$

점화식까지 나왔으니 이것을 코드로 표현해주면 문제는 풀린 것이나 다름없다.

풀이

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

int solution(int N, int number) {
    int answer = -1;
    vector<set<int>> dp;

    int temp = 0;
    for(int i=0; i < 9; i++){
        temp = 10*temp +N;
        if(temp == number)
        {
            return i+1;
        }
        set<int> s;
        s.insert(temp);
        dp.push_back(s);
    }

    for (int i=1; i<9; i++) { 
        for (int j=0; j<i; j++) {
            for (const auto & op1 : dp[j]) {
                for (const auto & op2 : dp[i-j-1]) {
                    dp[i].insert(op1+op2);
                    dp[i].insert(op1-op2);
                    dp[i].insert(op1*op2);

                    if (op2 != 0)
                        dp[i].insert(op1/op2);
                }
            }
        }

        if (dp[i].find(number) != dp[i].end()) {
            answer = i+1;
            break;
        }
    }
    return answer;
}