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

---

첫 시도

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

using namespace std;

int solution(int N, int number) {
    vector<unordered_set<int>> dp;
    dp.push_back(unordered_set<int>{N, N, N, N, N});
    int count = 0;
    bool whileBreak = true;
    while (whileBreak)
    {
        dp.resize(dp.size() + 1);
        unordered_set<int> chackSet;
        for (auto& def : dp[count])
        {
            chackSet.insert(def + N);
            chackSet.insert(def - N);
            chackSet.insert(def * N);
            chackSet.insert(def / N);
            chackSet.insert(stoi(to_string(def) + to_string(N)));

            if (chackSet.count(number) >= 1) {
                whileBreak = false;
                break;
            }
        }
        count++;
        if (count > 8)
            return -1;
    }
    return count;
}

실패

내용물에 대한 괄호처리를 정상적으로 진행하지 못했다.

N, NN, NNN, NNNN에 대한 처리만 진행함.

아마 괄호가 처음꺼 두번째꺼 NN + N / N 이런식은 감지가 되는데, NN + (N/N) 은 처리할 수 없기 때문인거 같다.

---

두 번째 시도

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

using namespace std;

int solution(int N, int number) {
    if(N == number) return 1;
    vector<unordered_map<int, string>> dp(9);
    for (int i = 1; i <= 8; i++) {
        string numString;
        for (int j = 0; j < i; j++) {
            numString += to_string(N);
        }
        dp[i].insert({ stoi(numString), numString });
    }

    for (int i = 2; i <= 8; i++) {
        for (int j = 1; j < i; j++)
            for (auto& def1 : dp[j])
                for (auto& def2 : dp[i - j]) {
                    dp[i].insert(pair<int, string>(def1.first + def2.first, def1.second + "+" + def2.second));
                    dp[i].insert(pair<int, string>(def1.first - def2.first, def1.second + "-" + def2.second));
                    dp[i].insert(pair<int, string>(def1.first * def2.first, def1.second + "*" + def2.second));

                    if(def2.first != 0)
                        dp[i].insert(pair<int, string>(def1.first / def2.first, def1.second + "/" + def2.second));
                }
        if (dp[i].count(number) >= 1) {
            std::cout << "Result :  " << dp[i][number] << std::endl;
            return i;
        }
    }
    return -1;
}

성공

도대체 왜 시도가 성공하지 못하는가 생각했더니 괄호문제인것 같아서.

단순 무식하게 첫번째 배열값부터 마지막 배열값 까지의 괄호처리를 전부 진행해버렸다.

동작과정이 두번제곱승으로 더 많아진게 흠이다.