[프로그래머스 lv3] N으로 표현 풀이

해설

숫자 number을 N과 사칙연산으로 표현할 때 N 사용 횟수의 최솟값을 구하는 문제이다.

최솟값이 8보다 크면 -1을 리턴하라고 했으므로, 우리는 1개부터 8개까지의 N을 사용했을 때 각각 만들 수 있는 수 목록을 찾으면 된다.

 

1) 1개의 N을 사용해서 만들 수 있는 수는 N 하나이다.

 

2) 2개의 N을 사용해서 만들 수 있는 수는

- N을 두개 이어 붙인 NN

- (1개의 N의 사용해서 만들 수 있는 수)와 (1개의 N의 사용해서 만들 수 있는 수)를 사칙연산한 결과이다.

 

3) 3개의 N을 사용해서 만들 수 있는 수는

- N을 세개 이어 붙인 NNN

- (1개의 N을 사용해서 만들 수 있는 수)와 (2개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과

- (2개의 N을 사용해서 만들 수 있는 수)와 (1개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과이다.

 

4) 4개의 N을 사용해서 만들 수 있는 수는

- N을 네개 이어 붙인 NNN

- (1개의 N을 사용해서 만들 수 있는 수)와 (3개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과

- (2개의 N을 사용해서 만들 수 있는 수)와 (2개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과

- (3개의 N을 사용해서 만들 수 있는 수)와 (1개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과이다.

 

....

 

정리해 보면, m개의 N을 사용해서 만들 수 있는 수는 다음과 같다.

- N을 m개 이어붙인 수

- for (int i=1; i<m; i++) {

    (i개의 N을 사용해서 만들 수 있는 수)와 (m-i개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과들

}

 

m = 1부터 m = 8까지 각각의 사용 개수에 대하여 만들 수 있는 수들을 모두 저장해둔다.

목록을 순회하며 number가 있으면 해당 개수를 리턴하고, 목록에 없다면 -1을 리턴한다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<set<int>> res(10);

int solution(int N, int number) {
    
    res[1].insert(N);
    
    for (int m=2; m<=8; m++) {
        
        int p = 1;
        int num = 0;
        for (int i=1; i<=m ;i++) {
            num += (N*p);
            p *= 10;
        }
        res[m].insert(num);
        
        for (int i=1; i<m; i++) {
            for (auto num1 : res[i]) {
                for (auto num2 : res[m-i]) {
                    res[m].insert(num1+num2);
                    res[m].insert(num1-num2);
                    res[m].insert(num1*num2);
                    if (num2) res[m].insert(num1/num2);
                }
            }
        }
    }
    
    for (int m=1; m<=8; m++) {
        if (find(res[m].begin(), res[m].end(), number) != res[m].end()) 
            return m;
    }
    return -1;
}