[Programmers] (고득점KIT) DP - N으로 표현

Sierra·2022년 2월 8일
0
post-thumbnail

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

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

Nnumberreturn
5124
2113

Solution

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

using namespace std;

int solution(int N, int number) {
    int answer = -1;
    unordered_set<int> s[8];
    int base = 0;
    for(int i = 0; i < 8; i++){
        base = 10 * base + 1;
        s[i].insert(base * N);
    }
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < i; j++){
            for(auto & op1 : s[j]){
                for(auto & op2 : s[i-j-1]){
                    s[i].insert(op1 + op2);
                    s[i].insert(op1 - op2);
                    s[i].insert(op1 * op2);
                    if(op2 != 0) s[i].insert(op1 / op2);
                }
            }
        }
        if(s[i].count(number) > 0) {
            answer = i + 1;
            break;
        }
    }

    return answer;
}

다이나믹 프로그래밍의 의의가 하나 있다면, 무작정 노가다로 찾아낼 수도 있는 값들이 있지만 그 중에서 중복 된 연산을 줄이고 과거에 계산했던 값들을 통해 현재 계산해야 하는 값을 빠르게 찾아내는 것 이라고 알고있다.

즉 처음부터 하나하나 찾아 올라가되, 자릿수가 올라감에 따라서 생길 수 있는 중복 값들은 정리해줄 필요가 있는 것이다.

결국 DP라는 건 일을 두번 하지 않기 위해 쓰는 것일테니까.

unordered_set<int> s[8];
int base = 0;
for(int i = 0; i < 8; i++){
    base = 10 * base + 1;
    s[i].insert(base * N);
}

우선 입력받은 N에 대하여 1의 자리부터 8의 자리까지의 데이터를 생성해서 각 자릿수별 set에 집어넣어둔다.

for(int i = 0; i < 8; i++){
    for(int j = 0; j < i; j++){
        for(auto & op1 : s[j]){
            for(auto & op2 : s[i-j-1]){
                s[i].insert(op1 + op2);
                s[i].insert(op1 - op2);
                s[i].insert(op1 * op2);
                if(op2 != 0) s[i].insert(op1 / op2);
            }
        }
    }
    if(s[i].count(number) > 0) {
        answer = i + 1;
        break;
    }
}

다음으로 겁나 노가다지만 각 자리마다 데이터들을 하나하나 끄집어내서 모든 값들에 대해 사칙연산을 하는 작업을 한번 시도해본다. set을 쓰는 이유는 이 과정에서 중복 된 값이 생겼을 시에 굳이 제거하지 않고 Binary Tree 내에서 알아서 처리되도록 하기 위해서다. (Set은 Binary Search Tree구조로 구성되어있다. 즉 중복 데이터가 존재한다면 insert 하지 않는다.)

이러한 노가다를 하더라도 set이기 때문에 자연스럽게 중복된 데이터는 피하게되고 시간이 절약된다. 각 자릿수 페이즈마다 만들고자 하는 값이 하나라도 만들어졌다면, break 처리한다. 가장 작은 자리부터 계산을 할테니까 가장 먼저 답이 나온놈이 즉 N을 최소한으로 사용해서 number를 만든 경우기 때문이다.

개인적으로 DP를 잘 못한다. 그렇지만 반드시 극복해야하는 문제라 생각한다. DP가 시험에 잘 나오지는 않는다 하더라도 실무에서는 언제든지 이런 개념을 써야할 상황이 생기지 않을까 싶다.

profile
블로그 이전합니다 : https://swj-techblog.vercel.app/

0개의 댓글