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

문제

프로그래머스 DP - N으로 표현

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

문제 설명

아래와 같이 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 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

 

---

문제 풀이

접근 방식

DP 문제의 핵심은 메모이제이션(Memoization)이다.

즉, 무엇을 DP에 저장할 것인가, 어떻게 중복을 최소화할 것인가가 중요하다.

 

우선, 무엇을 DP에 저장할지 파악하기 위해 사칙연산과 N을 조합해 보았다.

(Ni는 N i개로 만들 수 있는 숫자들, ㅁ은 사칙연산을 의미한다.)

 

1. N1 : N

2. N2 : N1ㅁN1, NN

3. N3 : N1ㅁN2, N2ㅁN1, NNN

4. N4 : N1ㅁN3, N2ㅁN2, N3ㅁN1, NNNN

위의 결과를 통해 DP[i]에는 N i개로 만들 수 있는 숫자들을 저장해야겠다고 생각하였다.

또한, Nk는 Ni와 Nj(i + j = k)의 조합으로 구성된다는 규칙성을 파악할 수 있었다.

(실제 코드에서는 0 <= i < 8으로 구현해서 i + j + 1 = k이어야 한다.)

 

 

DP[k] = DP[i] ㅁ DP[j] (i + j = k), NN..N(N으로만 이루어진 k자리 숫자)

 

 

다음으로 효율성을 높일 방법에 대해 고민해 보았다.

이전 단계의 DP 사이즈가 크면 다음 단계의 DP 사이즈는 기하급수적으로 커지기 때문에,

매 단계에서 DP 사이즈를 최소화하는 것이 효율성을 높이는 방법이라고 판단하였다.

그래서 중복 값의 제거와 불필요한 값의 제거를 통해 효율성을 높였다.

 

1) 중복 값 제거

 

DP를 vector로 구현 시, 중복 제거를 위해 다음의  방법을 사용한다.

#include <vector>
#include <algorithm>

sort(v.begin(), v.end());
v.erase(unique(v.begin(),v.end()),v.end());

하지만 set이라는 컨테이너를 활용하면 더 간단하게 중복 값을 제거할 수 있다.

set은 중복된 원소를 허용하지 않기 때문에 위와 같은 방법을 쓰지 않아도 중복 값이 제거된다.

set은 push_back이 아니라 insert로 원소를 삽입하며, 오름차순으로 정렬된다.

set을 사용하기 위해서는 아래의 헤더가 필요하다.

#include <set>

하지만 이 문제에서는 정렬을 할 필요가 없다.

set은 원소 삽입 시 정렬이 되는 구조이기 때문에, 원소 삽입이 빈번할 경우 효율이 떨어진다.

그래서 더 좋은 방법을 찾아보다 unordered_set을 알게 되었다.

unordered_set은 set과 비슷하나, 정렬이 자동으로 되지 않는다.

unordered_set을 사용하기 위해서는 아래의 헤더가 필요하다.

#include <unordered_set>

2) 불필요한 값 제거

 

N의 최소 개수로 number를 만드는 것이 목표이기 때문에 0은 불필요한 값이다.

÷연산을 할 때, 분모가 0이면 에러가 발생하기 때문에 더욱이 0은 존재하면 안 된다.

 

또한, －연산을 통해 도출되는 음수 값은 같은 절댓값을 가진 양수 값이 항상 존재한다.

이 값은 다음에 ＋,－연산을 수행하면 같은 결괏값을 도출하므로 불필요하다.

 

따라서 DP에는 양수만 존재하면 된다.

그래서 －연산과 ÷연산 시, 결괏값이 양수인지 확인하는 작업이 필요하다.

if (a - b > 0)
	DP[k].insert(a - b);
if (a / b > 0)
	DP[k].insert(a / b);

---

풀이 코드 - C++

#include <vector>
#include <unordered_set>

using namespace std;

int getNN(int N, int idx) {
	int result = N;
	for (int i = 1; i <= idx; i++) {
		result = result * 10 + N;
	}
	return result;
}

int solution(int N, int number) {
	if (N == number)
		return 1;

	vector<unordered_set<int>> DP(8);
	DP[0].insert(N);

	for (int k = 1; k < 8; k++) {
		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				if (i + j + 1 != k) continue;
				for (int a : DP[i]) {
					for (int b : DP[j]) {
						DP[k].insert(a + b);
						if (a - b > 0)
							DP[k].insert(a - b);
						DP[k].insert(a * b);
						if (a / b > 0)
							DP[k].insert(a / b);
					}
				}
			}
		}
		DP[k].insert(getNN(N, k));

		if (DP[k].count(number))
			return k + 1;
	}

	return -1;
}

 

실행 결과