[c++] 프로그래머스 동적계획법 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 합니다.

 

입출력 예

 

N	number	return
5	12	4
2	11	3

 

입출력 예 설명

 

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

 

---

나의 코드

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <iostream>

using namespace std;
vector<unordered_set<int>> set(10);

int solution(int N, int number) {
    int answer = 1000;
    for (int i = 1; i < 9; i++) {
        string tmp = "";
        for (int k = 0; k < i; k++) {
            tmp += to_string(N);
        }
        set[i].insert(stoi(tmp));
        if (stoi(tmp) == number && i < answer) answer = i;
    }
    for (int i = 2; i < 9; i++) {
        for (int k = 1; k < (i / 2) + 1; k++) {
            for (int t : set[k]) {
                for (int p : set[i - k]) {
                    set[i].insert(t + p);
                    set[i].insert(t * p);
                    int big = max(t, p);
                    if ((t + p - big) > 0)set[i].insert(big / (t + p - big));
                    if (t != p) {
                        set[i].insert(t - p);
                        set[i].insert(p - t);
                    }
                }
            }
        }
        auto index = set[i].find(number);
        if (index != set[i].end() && answer > i) {
            answer = i;
            return answer;
        }
    }
    if (answer == 1000) return -1;
    return answer;
}

 

동적계획법은 이전에 내가 계산한 값을 가지고 와서 활용하는 것이다.

 

여기서 나는 i를 내가 사용할 N의 개수로 정하고 k는 i가 될수 있는 경우의 수로 사용하였다.

 

예를 들어 i가 4일 경우 아래와 같은 경우의 수가 있다.

(0,4), (1,3), (2,2), (3,1), (4,0)

여기서 (2,2)까지만 사용하도록 코드를 사용하였다.

 

경우의 수를 구하고 해당 경우의 수에 해당하는 계산값을 구하였다.

예를 들어 (2,2)의 경우 2개의 N을 사용하여 구한 값을 서로 사칙연산하였다.

(해당 값은 for문을 돌며 이전에 계산되어 set 벡터에 저장되어 있다.)