[프로그래머스 LV3] - N으로 표현(DP - possible_sets) c++

문제

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

프로그래머스

접근방법

시간 내에 풀 수 있는 방법이 도저히 생각나지 않아서

GPT에게 물어봤다.

 

코드를 보고 놀랐다. 처음 보는 접근방식이었다.

2차원 배열 dp를 이용해 풀 수 있을까 생각해봤지만,

그 방법이 떠오르지 않았는데

코드를 보고 이마를 한 대 쳤다.

 

n이 8번 가는 동안,

그 사이 만들어진 수식들을 저장한다.

 

다음 i번째에는

i-j와 j 번째 배열에 있는 수식들을 이용해

i번째 possible_sets배열을 채운다.

코드

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

using namespace std;

int solution(int N, int number) {
    vector<unordered_set<int>> possible_sets(9);
    
    // N을 1개부터 8개까지 사용하여 만들 수 있는 숫자 조합 계산
    for (int i = 1; i <= 8; ++i) {
        string str_n = to_string(N);
        str_n = string(i, str_n[0]); // N을 i번 반복하여 만든다
        
        possible_sets[i].insert(stoi(str_n));
        
        // 가능한 숫자 조합 계산
        for (int j = 1; j < i; ++j) {
            for (const int& x : possible_sets[j]) {
                for (const int& y : possible_sets[i - j]) {
                    possible_sets[i].insert(x + y);
                    possible_sets[i].insert(x - y);
                    possible_sets[i].insert(x * y);
                    if (y != 0)
                        possible_sets[i].insert(x / y);
                }
            }
        }
        
        // 목표 숫자가 만들어졌을 경우 최솟값 반환
        if (possible_sets[i].count(number))
            return i;
    }
    
    // 목표 숫자가 만들어지지 않을 경우 -1 반환
    return -1;
}

개선할 점

...