프로그래머스 N으로 표현

프로그래머스에서 DP 문제를 찾아보고 나온 문제이다. 가장 쉬운 문젠데 역시 DP는 어렵다....

 

DP 배열은 dp[i] : i개의 숫자를 가지고 만들 수 있는 숫자 를 저장한다.

처음 DP를 초기화할때, 그 갯수만큼의 숫자를 저장해둔다. (예를 들어, dp[1] = 5, dp[2] = 55 ...)

그리고, 최대 8개까지 사용하는지 확인하는 것이므로, 8까지(사용 가능한 숫자 개수) 루프를 돌면서 dp 탐색을 한다.

만약 N = 5이고, 탐색하는 루프 수(숫자 개수)가 5이면, 5(op)5555 55(op)555 555(op)55 5555(op)5 이렇게 나눌 수 있다. 5를 1개 사용한 숫자들과 4개 사용한 숫자들의 연산 결과가 dp[5]에 추가되고, 2개와 3개의 연산, 3개와 2개의 연산, 4개와 1개의 연산결과도 추가된다.

 

이것을 일반화 시키면, i = 0 ~ 루프 수(숫자 개수)일때 dp[j] 의 숫자와, dp[i - j]의 숫자 연산 결과들이 dp[i]에 들어간다고 생각하면 된다.

그렇게 탐색하던 중, dp[i]를 전부 채운 다음, 우리가 원하는 숫자가 있는지 확인하여 있다면 i를 리턴하면 답이다!

---

#include <string>
#include <vector>
#include <cstdlib>
#include <iostream>
using namespace std;


int solution(int N, int number) {
    int answer = 0;
    vector<vector<int> > dp(10, vector<int>(0));
    string temp = "";
    for (int i = 1; i <= 9; i++) // 같은 숫자로 이루어진 number 들 생성.
    {
        temp += char('0' + N);
        dp[i].push_back(atoi(temp.c_str()));
        if (number == dp[i][0]) // number가 현재 만든애랑 같으면 그냥 리턴해버리기
            return (i);
    }
    for (int i = 2; i < 9; i++) // N이 2개 이상 ~ 8개까지 확인
    {
        for (int j = 1; j < i; j++) // 개수를 쪼개가며 확인 5/5555 55/555 555/55 5555/5
        {
            for (auto a : dp[j]) // 1개일때, 2개일때 ...
            {
                for (auto b : dp[i - j]) // i - 1개일때, i - 2개일때...
                {
                    dp[i].push_back(a + b); //숫자들 사칙연산을 넣기.
                    dp[i].push_back(a - b);
                    dp[i].push_back(a * b);
                    if (b)
                        dp[i].push_back(a / b);
                }
            }
        }
        for (auto candid: dp[i])
        {
            if (candid == number)
                return i;
        }
    }
    return -1;
}

 

뭔가 이전의 DP 문제들은, 방문표시나 횟수와 같은것을 셀에 기록만 했던것 같다. 이번 문제는 아예 해당 자리에 가능한 숫자들을 저장한다. 이 경우에는 vector를 써야한다... 언제든지 넣을 수 있게 만들 수 있으니 풀이가 좀 쉬워진 것 같다.

백준 말고도 다른 곳 문제들도 재미있는게 많은 것 같다. 여기저기서 한번 풀어봐야겠다!

 

오늘도 평온한 하루가 되길. 슨민.