[프로그래머스] N으로 표현 | C/C++

문제

입출력

N	number	return
5	12	4
2	11	3

풀이

DP 집중 풀이 시작 .. DP를 너무 못 해서,,,, 

• DP 접근 방법 

1. 2+2 2/2
2. 22+2/2

2번에서 "22"는 "2"를 두 번 반복해서 쓰임 -> 사칙연산으로 결합한 결과임을 알 수 있다.

--> 이 부분이 DP(동적 계획법)을 사용한다! 다음 것이 이전 것을 사용한다는 점!

---> 이미 계산한 결과는 배열에 저장하기 때문에 나중에 동일한 계산을 할 때는 저장된 값을 반환하여 계산을 함.

 

• DP 배열 구성

N의 개수로 먼저 나누는 게 중요하다. 

N이 1일 때 DP[0] :  1개의 N으로 만들 수 있는 수들의 집합 -> N 

N이 2일 때  DP[1] :  2개의 N으로 만들 수 있는 수들의 집합 -> NN, N+N, N-N, N*N, N/N

N이 3일 때  DP[2] :  3개의 N으로 만들 수 있는 수들의 집합 -> NNN, NN+N, NN-N, NN*N, NN/N, (N+N)+N, (N+N)-N, (N+N)*N. (N+N)/N, (N-N)+N, (N-N)-N, (N-N)*N, (N-N)/N, (N*N)+N, (N*N)-N, (N*N)*N, (N*N)/N, (N/N)+N, (N/N)-N, (N/N)*N, (N/N)/N 

.

.

.

N이 K일 때 DP [K-1] : K개의 N으로 만들 수 있는 수들의 집합 -> NNN..(K개의 N),  DP [i] ㅁ DP [j](i+j=k) 

 

• unordered_set을 택한 이유

처음에는 set을 막연하게 생각했지만 배우는 과정이어서 다른 블로그들을 참고하다가 DP벡터 안에 각 집합은 정렬될 필요가 없으므로 set 보다 unordered_set을 사용하는 것이 더 효율적이라는 것을 알아냈다. 그리고 set은 중복을 허용하지 않기에 이 점도 꼭 필요한 부분이다.

vector<unordered_set<int>> DP(8);

 

 

 

 

 

#include <string>
#include <unordered_set>

using namespace std;

int solution(int N, int number) {
    int answer = -1; // 최솟값이 8보다 크면 -1을 return
    unordered_set<int> s[8]; // 정렬할 필요 없, 중복제거는 필요

    int sum = 0;
    for (int i = 0; i < 8; ++i) { //NN 조합 
        sum = 10 * sum + N;
        s[i].insert(sum);
    }

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

    // set을 채웠으니 number가 set에 들어가 있는지 여부 확인
    for (int i = 0; i < 8; ++i) {
        if (s[i].find(number) != s[i].end()) {
            answer = i + 1;
            break;
        }
    }


    return answer;
}


int main()
{
	solution(5, 12);
	return 0;
}

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=cpp

프로그래머스