[프로그래머스/C++] N으로 표현

(6/20 - X)

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

코딩테스트 연습 - N으로 표현

 

 

구현

1. N을 1개 사용하여 만든 집합을 N1, N을 2개 사용하여 만든 집합을 N2, N을 3개.. 박스에 넣는다고 생각하자. (중복되지 않는 원소를 갖는 unordered_set을 사용)

2. N1을 만들면서 컨테이너에 number와 값이 같은 수가 있는지 확인한다. 있으면 1을 return하는 식. 없다면 N2를 만들고, 또 없다면 N3을 만들고.. N7까지 만들어도 없다면 -1을 return한다.

 

1번을 구현하는 게 어렵다. 수 조합을 어떻게 만드냐 싶은데, 아래와 같이 그림을 그리면서 보면 패턴이 나온다.

 

 

 

 

코드

// [프로그래머스 코테 고득점 Kit] dynamic programming - n으로 표현
#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>

using namespace std;

int make(int N, int p){//i=2일때 NN = N * 10 + N, i=3일때 NNN = N * 100 + N * 10 + N, i=4일때 NNNN..
    int value = 0;
    for (int i = 1; i <= p; i++) {
        value += N * pow(10, i - 1);
    }
    return value;
}

int solution(int N, int number) {
    int answer = 0;

    if (N == number) return 1;

    vector<unordered_set<int>> box(9);
    
    box[1].insert(N); // N1에는 N 하나만
    for (int i = 2; i < 9; i++) { //i3
        box[i].insert(make(N, i)); 
        for (int j = 1; j < i; j++) { //j=1,1<3,i-j==2 // j=2,2<3,i-j==1 //
            for (auto& num_first : box[j]) {
                for (auto& num_second : box[i - j]) {
                    box[i].insert(num_first + num_second);
                    box[i].insert(num_first - num_second);
                    box[i].insert(num_first * num_second);
                    if(num_second != 0)
                        box[i].insert(num_first / num_second);
                    box[i].insert(num_second + num_first);
                    box[i].insert(num_second - num_first);
                    box[i].insert(num_second * num_first);
                    if (num_first != 0)
                        box[i].insert(num_first / num_first);
                }
            }
        }
        if (box[i].end() != box[i].find(number)) {
            answer = i;
            return answer;
        }
    }

    return -1;
}

int main() {
    solution(5, 12);
}