프로그래머스 문제 - N으로 표현

프로그래머스 N으로 표현 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

숫자 N만을 사용하여 사칙연산만으로 숫자number를 표현해야 합니다.
예를 들어 숫자 5를 사용하여 12를 만들려면
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
3가지가 존재하며 5의 사용횟수는 순서대로 6, 5, 4개를 사용하였습니다. 이 중 사용한 횟수가 작은 경우는 4입니다.
위와 같이 표현하였을때 숫자를 만드는 경우 중 사용횟수의 최소값을 구해야합니다.

문제 풀이

문제를 보고 완전탐색을 돌리기엔 시간초과가 나올 줄 알았지만 제한사항에 return값이 8이 넘는 경우라면 -1을 리턴하라는 값을 보고 충분히 완전탐색이 가능하다는 결론을 내렸습니다.

즉 배열을 만들어서 하나씩 값을 계산해나가면 답을 찾아낼 수 있습니다.
숫자 1개만 사용한다면 N밖에 만들지 못합니다.
숫자 2개를 사용한다면 N+N, N-N, N*N, N/N, NN값이 나옵니다.
숫자 3개를 사용한다면 (2개만 사용한 경우 - 1개만 사용한 경우), (1개만 사용한 경우 - 2개만 사용한 경우)들이 나옵니다. 즉

dp(n) = dp(i) + dp(n-i) //i는 1부터 n-1까지

라는 점화식이 나옵니다.
여기서 중요한 점은 숫자 5를 55, 555등 n만큼 N을 연속해서 붙여 사용하는 경우가 존재합니다.
사칙연산이 끝난 값 뒤에 붙이는 것이 아닌 N을 n만큼 붙인 값을 사칙연산에 사용하는 것이므로 모든 사칙연산을 끝내고 값을 넣은 배열 마지막에 값을 추가해주면 사칙연산을 같이 진행하게 됩니다.

한 사칙연산이 끝나게 되면 나온 값들을 number와 비교하여 같다면 바로 return해주면 되고 마지막까지 같은 값이 나오지 않는다면 -1을 리턴해주면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<long long> dp[9];
int Num;

void solve(int a, int b, int n)
{
    for(int i = 0; i < dp[a].size(); i++)
    {
        for(int j = 0; j < dp[b].size(); j++)
        {
            dp[n].push_back(dp[a][i] + dp[b][j]);
            dp[n].push_back(dp[a][i] - dp[b][j]);
            dp[n].push_back(dp[a][i] * dp[b][j]);
            if(dp[b][j] != 0)
            {
                dp[n].push_back(dp[a][i] / dp[b][j]);
            }
        }
    }
    dp[n].push_back((dp[n-1][dp[n-1].size()-1] * 10) + Num);
}

int solution(int N, int number) {
    int answer = 0;
    Num = N;
    dp[1].push_back(N);
    if(N == number)
    {
        return 1;
    }
    for(int k = 2; k <= 8; k++)
    {
        for(int i = 1; i < k; i++)
        {
            solve(i, k-i, k);  
        }
        for(int i = 0; i < dp[k].size(); i++)
        {
            if(dp[k][i] == number)
            {
                return k;
            }
        }
    }
    
    return -1;
}

출저

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