[프로그래머스] [C++] N으로 표현 (dp)

1. 문제

 

이 문제는 N 과 number가 주어진다.

 

이때 N은 1~9 의 수이며

 

11, 222, 3333, 33 , 444, 8 등과 같이 N을 여러개 이어붙인거에 덧셈 곱셈 뺄셈 나눗셈하여

 

number를 만드는 최소 N의 개수를 구하는 문제이다.

 

 

2. 문제 변형

주어진 N을 x라 할때 다음과 같은 배열을 만들어 조합탐색해나가면 문제를 해결할 수 있다.

 

[ x, xx, xxx, xxxx, xxxxx, xxxxxx, xxxxxxx, xxxxxxxx ]

 

이 배열 원소들이 그래프의 정점이라고 가정하고

 

간선은 연산이라고 생각하여 dfs를 돌리면 답을 얻을 수 있다.

 

이때 그래프의 형태는 한정점에서  한정점까지 4개의 방향간선이 뻗어나가, 간선의 개수가 많아진다.

 

이를 암시적 그래프 형태로 표현하여 간선을 신경쓰지 않고 문제를 해결할 수 있다. 

 

 

3. 동적계획법

이 문제에서 영향을 주는 요소는 두가지이다.

 

현재 몇개의 N을 썼는지?

 

현재 만들어진 식은 어떻게 되는지?

 

이 두가지의 영향을 받아 답이 결정되고, 각각 경우의 수마다 반복되는 계산이 생기게 된다.

 

따라서 이 두가지를 따로 메모이제이션하면 중복되는 계산을 다시하지 않을 수 있다.

 

 

 

4. 코드

 

 

#include <string>
#include <vector>
#include <map>
 
using namespace std;
vector<int> makeGraph(int N)
{
    vector<int> ret;
    int tmp{0};
    for(int i = 1; i <= 8; i++)
    {
        tmp = tmp*10 + N;
        ret.push_back(tmp);
    }
    return ret;
}
map<int, int> cache[9];
int dp(vector<int>& nSet, int number, int c, int expr)
{    
    if(expr == number) return c;
    if(cache[c].count(expr) != 0)
        return cache[c][expr];
    
    int ret = 9;
    
    for(int i = 0; i < nSet.size(); i++)
    {
        if(c + i + 1 > 8) continue;
        ret = min(ret, dp(nSet, number, c + i + 1, expr + nSet[i]));
        ret = min(ret, dp(nSet, number, c + i + 1, expr * nSet[i]));
        ret = min(ret, dp(nSet, number, c + i + 1, expr - nSet[i]));
        ret = min(ret, dp(nSet, number, c + i + 1, expr / nSet[i]));
    }
    cache[c][expr] = ret;
    return ret;
}
 
int solution(int N, int number) {
    int answer = 0;
    vector<int> nSet = makeGraph(N);
    answer = dp(nSet, number, 0, 0);
    if(answer == 9)
        answer = -1;
    return answer;
}

 

 

Algorithm/ExpressedAsN.cpp at master · Nor-s/Algorithm (github.com)

코딩테스트 연습 - N으로 표현 | 프로그래머스 (programmers.co.kr)