[프로그래머스] N으로 표현

문제 링크

 

풀이

많은 DP 문제가 그렇듯 점화식만 제대로 세울 수 있으면 어렵지 않은 문제이지만, 꽤 까다로운 문제에 속하는 것 같습니다. 여기에서 d[i]는 solution 함수의 매개변수로 주어지는 N을 i번 사용해서 얻을 수 있는 숫자의 집합으로 정의해 문제를 풀면 수월합니다. 즉 N이 5라면 다음과 같은 점화식을 만들 수 있습니다.

 

d[1] = {5}

d[2] = {55, 5+5, 5-5, 5*5, 5/5}

d[3] = {555, (5+5) + 5, (5+5) - 5, (5+5) * 5, ... , 55 / 5}

 

3번째 항부터는 집합의 크기가 커지기 시작합니다. 우리는 규칙을 찾아야 하고요. 일단 N이 i만큼 붙어 있는 숫자 하나는 만들기 쉽습니다. d[4]에는 5555가 있겠지요.

 

d[2]를 보면 55를 제외하고는 d[1]의 요소를 통해 이항 연산을 하고 있습니다. d[1] +-*/ d[1입니다. d[3]의 두 번째 요소를 보면 두 번째 항과 첫 번째 항의 조합입니다. 정리를 하면 (d[1] +-*/ d[2]) + (d[2] +-*/ d[1])의 경우의 수를 전부 찾으면 됩니다. 물론 덧셈과 곱셉 연산에 한해서는 d[1] * d[2]과 d[2] * d[1]은 똑같습니다. 이 중복을 거르기 위한 루틴을 넣기 보다는 유일한 값만 저장할 수 있는 set 컨테이너를 사용하는 편이 빠릅니다. 문제에서 최솟값이 8보다 크면 -1을 리턴하라고 했기 때문에 우리는 d[8]까지만 구하면 됩니다. 최종 점화식은 다음과 같습니다.

 

d[n] = (d[1] +-/* d[n-1]) + (d[2] +-/* d[n-2]) + ... + (d[n-1] +-/* d[1])

 

반복문이 4개가 나오는데요. 가장 바깥은 2~8입니다. d[1]에는 확실하게 하나의 값이 들어가니까 굳이 반복문 루틴 안에 넣어주지 않았습니다. 위 공식에 맞춰서 반복문을 작성해주면 됩니다.

 

코드

#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>
using namespace std;

int solution(int N, int number) 
{
    int answer = -1;
    vector<unordered_set<int>> d(9);
    for (int i = 1; i <= 8; ++i)
    {
        int num = 0, count = i;
        while (count-- > 0)
            num += N * pow(10, count);
        d[i].insert(num);
    }
    for (int i = 2; i <= 8; ++i)
    {
        for (int j = 1; j < i; ++j)
        {
            for (const auto a : d[j])
            {
                for (const auto b : d[i - j])
                {
                    auto& dd = d[i];
                    dd.insert(a + b);
                    dd.insert(a * b);
                    dd.insert(a - b);
                    if (b != 0)
                        dd.insert(a / b);
                }
            }
        }
    }
    for (int i = 1; i <= 8; ++i)
    {
        if (d[i].find(number) != d[i].end())
            return i;
    }
    return answer;
}

set과 unordered_set의 성능 차이는 다음과 같습니다. set은 균형 이진 트리로 구현됐기 때문에 정렬이 수행되지만 unordered_map은 해시로 구현됐기에 정렬되지 않습니다. 특정 구간까지는 unordered_map이 빠르지만 데이터가 많아지면 해시 충돌이 발생해 성능이 떨어질 수 있습니다. 이 문제는 예제의 크기가 크지 않으므로 unordered_set이 유리합니다.

set

unordered_set