프로그래머스 : 동적계획법(Dynamic Programming) > N으로 표현(lv3) c++

프로그래머스 링크

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

프로그래머스

코드 풀이

N = 5이라고 할때

N1 = N

N2 = N + N, N - N, N * N, N / N, NN

N3 = N1 ㅁ N2, N2 ㅁN1, NNN

N4 = N1 ㅁ N3, N2 ㅁ N2, N3 ㅁ N1, NNNN

이 되는것을 볼 수 있다.

공식 : Ni ㅁ Nj, j = i - j - 1이 나오는것을 확인 할 수 있다.

i - j - 1 은 쉽게 생각해서 첫번째와 마지막인덱스값을 연산하고 두번째와 마지막 인덱스 - 1번째값을 연산한다는 개념이다.

코드

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

using namespace std;

int solution(int N, int number) {
    int answer = -1;
    
    // N이랑 number이랑 같다면 바로 1리턴
    if(N == number)
        return 1;

    // unordered_set은 중복된 값을 제외시켜버려서 해당 자료구조를 선택
    vector<unordered_set<int>> dp(8);

    // N이 한개일때는 N고정이기 때문에 바로 넣어줌.
    dp[0].insert(N);

    for (int i = 1; i < 8; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            for (int a : dp[j])
            {
                for (int b : dp[i - j - 1])
                {
                    dp[i].insert(a + b);
                    dp[i].insert(a - b);
                    dp[i].insert(a * b);
                    if (a != 0 && b != 0)
                        dp[i].insert(a / b);
                }
            }
        }

        // N으로만 이루어진 숫자들을 넣어주기 위한 구역
        int Add = N;

        for (int k = 1; k <= i; ++k)
        {
            Add = Add * 10 + N;
        }

        dp[i].insert(Add);

        // dp의 i번째 인덱스에 number라는 값이 탐색된다면
        // 탐색된 값이 최소값이므로 바로 해당 인덱스 + 1을 리턴해준다.
        if (dp[i].count(number))
        {
            answer = i + 1;
            break;
        }
    }

    return answer;
}

정확성