프로그래머스 42895 N으로 표현

문제

문제 분석

나는 그냥 DP로 풀었다.

현재 N의 갯수가 i라고 할 때 가능한 모든 경우의 수를 DP[i][something]에 저장하자고 하고 1부터 i-1까지는 모두 다 정확하게 정의되어 있다고 하자.

그렇다면 i는 다음과 같이 2개로 나눌 수 있다.

(1, i-1), (2, i-2), (3, i-3) ...(i-1, 1)

그리고 이렇게 분할된 두개의 조각에 존재하는 모든 조합의 사칙연산의 결과값을 DP[i][idx]에 저장한다.

이렇게 하다보면 결국에는 될것이다.

이걸 dfs로써 풀 수 있다고 하는데 그런 분들의 코드를 보면 하나같이 왼쪽의 데이터를 새로운 데이터로 구성하고 오른쪽은 고정된 값들 ( temp = temp * 10 + N / 즉 N, NN, NNN등)으로만 구성하던데 이렇게 하면 예외가 존재한다.

5로 4을 만든다 -> 5-(5/5)와 같이 뒷 부분이 먼저 연산되는 경우를 알아낼 수 없다.

근데 맞다고 하는데 왜 되는지는 모르겠다.

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;

int count_arr[10000000] = {0};
lld output = MY_INT_MAX;
vector<vector<lld>> dp;

int get_n_k(int k, int n)
{
    int return_val = n;
    for(int i=1; i<k; i++)
        return_val = return_val * 10 + n;
    return return_val;
}

int solution(int n, int number)
{
    vector<lld>dummy_v;
    dp.push_back(dummy_v);
    for(int i=1; i<=8; i++)
    {
        vector<lld>tmp_v;
        tmp_v.push_back(get_n_k(i, n));
        if(tmp_v[0] == number)
            return i;

        for(int k=1; k<i; k++)
        {
            for(int a=0; a<dp[k].size(); a++)
            {
                for(int b=0; b<dp[i-k].size(); b++)
                {
                    lld tmp_1 = dp[k][a] + dp[i-k][b];
                    lld tmp_2 = dp[k][a] * dp[i-k][b];
                    lld tmp_3 = dp[k][a] - dp[i-k][b];
                    lld tmp_4 = dp[k][a] / dp[i-k][b];
                    if(tmp_1 == number || tmp_2 == number || tmp_3 == number || tmp_4 == number)
                        return i;

                    if(tmp_1 < 1000000 && tmp_1 > 0 && count_arr[tmp_1] == 0)
                    {
                        count_arr[tmp_1] = k;
                        tmp_v.push_back(tmp_1);
                    }
                    if(tmp_2 < 1000000  && tmp_2 > 0 && count_arr[tmp_2] == 0)
                    {
                        count_arr[tmp_2] = k;
                        tmp_v.push_back(tmp_2);
                    }
                    if(tmp_3 > 0 &&  tmp_3 > 0 && count_arr[tmp_3] == 0)
                    {
                        count_arr[tmp_3] = k;
                        tmp_v.push_back(tmp_3);
                    }
                    if(tmp_4 > 0  && tmp_4 > 0 && count_arr[tmp_4] == 0)
                    {
                        count_arr[tmp_4] = k;
                        tmp_v.push_back(tmp_4);
                    }
                }
            }

        }
        dp.push_back(tmp_v);
    }
    return -1;
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    int a,b;
    cin >> a >> b;
    cout << solution(a,b);
    return 0;
}

개선점?

나는 2차원 벡터를 사용했는데 다른 사람은 1~i-1을 참조하여 i의 경우의 수들을 저장하는 set을 리턴하는 함수를 정의하여 쉽게 푸는 경우가 있었다.

"자료형도 리턴 가능하고, 어차피 heap영역에 원소들이 저장되고 STL이 효과적으로 설계되어 있으므로 모든 원소를 복사하는 비용은 들지 않는다"

www.delftstack.com/howto/cpp/how-to-return-a-vector-from-a-function-efficiently-in-cpp/

Return a Vector From a Function in C++