[프로그래머스]동적계획법(Dynamic Programming) : N으로 표현 (level 3) (c++)

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

코딩테스트 연습 - N으로 표현

 

#include <iostream>

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

const int MAX = 8;

// aim을 만드는 N의 최소 개수를 반환
int go(vector<unordered_set<int>>& v_set, int cnt, int aim)
{
    // 개수가 8 초과이면 -1 반환
    if (cnt > MAX)
    {
        return -1;
    }

    /*
        두 숫자를 이루는 N의 개수가 cnt개인 set들의 숫자로 사칙연산 후
        만들어진 숫자를 v_set[cnt]에 insert
        
        ex) cnt = 3 일때, v_set[1]의 숫자들 ~ v_set[2]의 숫자들 연산 결과를 v_set[3]에 insert
                          v_set[2]의 숫자들 ~ v_set[1]의 숫자들 연산 결과를 v_set[3]에 insert
    */
    for (int i = 1; i < cnt; ++i)
    {
        for (int num1 : v_set[i])
        {
            for (int num2 : v_set[cnt - i])
            {
                v_set[cnt].insert(num1 + num2);
                v_set[cnt].insert(num1 - num2);
                v_set[cnt].insert(num1 * num2);

                if (num2 != 0)
                {
                    v_set[cnt].insert(num1 / num2);
                }
            }
        }
    }

    // v_set[cnt]에서 목표한 숫자를 찾으면 cnt반환 (= 최소 개수)
    if (v_set[cnt].find(aim) != v_set[cnt].end())
    {
        return cnt;
    }

    // 찾지 못했다면 cnt + 1로 go함수 재귀호출
    return go(v_set, cnt + 1, aim);
}

int solution(int N, int number) {
   
    // v_set[cnt] : N을 cnt번 사용한 숫자들의 set
    vector<unordered_set<int>> v_set(MAX + 1);
    
    /*
        숫자 N, NN, NNN ... NNNNNNNN을 미리 각 집합에 넣어줌.
        
        ex) N은 v_set[1]에, NNN은 v_set[3]에 insert
    */
    int base = 0;
    for (int i = 1; i <= MAX; ++i)
    {
        base = base * 10 + N;
        v_set[i].insert(base);
    }

    // number를 만드는 N의 최소 개수를 반환. 개수가 8 초과이면 -1 반환
    return go(v_set, 2, number);
}

 

처음으로 푸는 level 3 dp 문제였다. 좀 어렵긴 하구나 ㅜㅜ

문제의 요구사항과 조건은 다음과 같다.

<요구사항>
숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중
N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

<조건>
N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
최솟값이 8보다 크면 -1을 return 합니다.

 

브루트 포스로 가능은 하겠지만...

dp를 사용하면 더 빨라질 거라고 예상할 수 있다.

그렇다면 위 문제를 보고 저장할 숫자의 기준을 무엇으로 삼을지 어떻게 판단할까??

 

 

<요구사항>
숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 
N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

<조건>
N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
최솟값이 8보다 크면 -1을 return 합니다.

 

N 사용횟수다!

나도 N에 홀려서 한참 헤맸지만.. 문제에서 요구하는 기준은 N을 사용한 횟수이므로,

사용 횟수 별로 묶어서 숫자들을 저장해야 한다.

 

 

숫자 저장 기준을 파악했으니, 이제 유의할 점을 찾아보자. 예시를 들겠다.

ex1)
(5) - (5 / 5) = 4  (O)
(5 / 5) - (5) = -4 (X)

ex2)
(5 + 5) / (5) = 2  (O)
(5) / (5 + 5) = 0  (X)

예시에서 사용한 수는 각각 (N을 1개 사용한 수)와 (N을 2개 사용한 수)의 연산이다.

결과는 N을 3개 사용한 수가 된다.

하지만 보다시피 뺄셈과 나눗셈의 경우, 두 수의 순서에 따라 구할 수 있는 값이 달라진다.

 

 

따라서

1. N을 □개 사용한 수들의 set을 만들고,

2. 각 set의 수를 앞뒤로 한번씩 연산한 후,

3. 해당하는 set에 넣어야 한다!

 

 

이에 해당하는 코드가 아래코드다. 위에서 부분만 짤라왔다.

// v_set[cnt] : N을 cnt번 사용한 숫자들의 set
vector<unordered_set<int>> v_set(MAX + 1);


... ... ... ... ...


/*
    두 숫자를 이루는 N의 개수가 cnt개인 set들의 숫자로 사칙연산 후
    만들어진 숫자를 v_set[cnt]에 insert
    
    ex) cnt = 3 일때, v_set[1]의 숫자들 ~ v_set[2]의 숫자들 연산 결과를 v_set[3]에 insert
                      v_set[2]의 숫자들 ~ v_set[1]의 숫자들 연산 결과를 v_set[3]에 insert
*/
for (int num1 : v_set[i])
{
    for (int num2 : v_set[cnt - i])
    {
        v_set[cnt].insert(num1 + num2);
        v_set[cnt].insert(num1 - num2);
        v_set[cnt].insert(num1 * num2);

        if (num2 != 0)
        {
            v_set[cnt].insert(num1 / num2);
        }
    }
}

 

 

cnt는 go함수가 재귀호출 되면서 1씩 늘어나므로,

목표 수 aim에 가장 처음으로 도착한 cnt가 최소 개수이다. 

// v_set[cnt]에서 목표한 숫자를 찾으면 cnt반환 (= 최소 개수)
if (v_set[cnt].find(aim) != v_set[cnt].end())
{
    return cnt;
}

 

 

끝