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 함수를 작성하세요.

 

 

 

 

입출력 예시

---

 

NUMBER	N	RETURN
5	12	4
2	11	3

 

 

 

 

접근법

---

1. 동적 계획법으로 접근을 해주는데, dynamic_results 에는 숫자 n 으로 i 개 표현할 수 있는 값들이 모두 들어간다.
2.  < j  개의 숫자 n 으로 표현 가능한 수 >  과 < i - j 개의 숫자 n  으로 표현 가능한 수 > 을 합쳐 < i 개의 n 으로 만들수 있는 숫자 > 를 구해준다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int nstr_int(int N, int num) {
    int k  = N;
    for(int i = 0; i < num - 1 ; i++) {
        k *= 10;
        k += N;
    }
    return k;
}


int solution(int N, int number) {
    vector<vector<int>> dynamic_results;
    dynamic_results.push_back({0});
    dynamic_results.push_back({N});
    if (N == number) 
        return 1;
    
    for (int i = 2 ; i < 9 ; i++) {
        vector<int> tmp = {nstr_int(N,i)};
        for (int j = 1 ; j < i/2 + 1 ; j++) {
            for(auto x : dynamic_results[j]) {
                for(auto y : dynamic_results[i-j]) {
                    tmp.push_back(x+y);
                    tmp.push_back(x-y);
                    tmp.push_back(y-x);
                    tmp.push_back(x*y);
                    if (x != 0)
                        tmp.push_back(y / x);
                    if (y != 0)
                        tmp.push_back(x / y);
                }
            }
        }
        if (find(tmp.begin(), tmp.end(), number) != tmp.end()) {
            return i;
        }
        dynamic_results.push_back(tmp);
    }
    
    
    int answer = 0;
    return -1;
}

https://programmers.co.kr/learn/courses/30/lessons/42895