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

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

풀이

DP(동적계획법)를 이용한 것은 알겠는데 어떻게?라는 부분이 쉽게 머리에 와닿지 않았다. 그리고 괄호를 사용할 수 있다는 조건이 어려웠다.

하지만 생각해보면 N을 몇번 사용한 값들을 저장할 때 수식이 아닌 값으로 저장하고 있고, 모든 조합을 가지고 있기 때문에 수식과 동일한 결과를 적어도 한번은 포함한다고 볼 수 있다.

N을 i번 사용할 때 얻을 수 있는 값

• NNNN...N (i만큼의 길이)
• 1번 사용한 값들 사칙연산 i-1번 사용한 값들
• 2번 사용한 값들 사칙연산 i-2번 사용한 값들
• ...
• n-1번 사용한 값들 사칙연산 i번 사용한 값들

※ 다음에 DP문제가 나온다면 먼저 작은 문제로 쪼개 보고, 규칙을 찾아봐야겠다.

동적 계획법(Dynamic Programming)

작은 문제로 나누어 부분 문제를 풀고, 이 해를 조합하여 전체 문제의 해답을 얻는 방법

코드

#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 sum = 0;
    for(int i = 0 ; i < 8 ; i++){
        sum = sum * 10 + N;
        s[i].insert(sum);
    }

    for(int i = 1 ; 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)){
            answer = i + 1;
            break;
        }
    }
    return answer;
}