[프로그래머스/C++] N으로 표현 (DP 문제 연습)

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

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

---

해당 문제는 DP 유형의 문제였는데 처음 풀어보는 유형이라 너무너무너무너무 어려웠다.

 

우선, 처음 문제를 보자마자 생각한 풀이방법으론 숫자 N을 몇번 사용하는지에 따라 dp[i] 배열을 초기화하고, 이전 dp 내용들을 기반으로 새로운 사칙연산 조합을 만드는 것이다.

 

5를 사용하는 경우를 예시로 들어보자.

5를 1번 사용 : 5
5를 2번 사용 : 55, 5+5, 5-5, 5*5, 5/5
5를 3번 사용 : 555, 5+(5+5), 5-(5+5), 5*(5+5), 5/(5+5)
                                5+(5-5), 5-(5-5), 5*(5-5), 5/(5-5)
                                5+(5*5), 5-(5*5), 5*(5*5), 5/(5*5)
                                5+(5/5), 5-(5/5), 5*(5/5), 5/(5/5)

                               55+5, 55-5, 55*5, 55/5
                               5+55, 5-55, 5*55, 5/55

 

숫자 N이 5라고 했을때, dp[0]은 5를 1번 사용한 경우이고, dp[1]은 5를 2번 사용한 경우, dp[2]는 5를 3번 사용한 경우로 하였다.

위 예시에서 5를 3번 사용한 경우를 보면, 결국 5를 1번 사용한 경우와 5를 2번 사용한 경우의 조합으로 만들어나갈 수 있다. 또한, +와 *의 경우엔 상관없지만 - 와 / 의 연산자는 피연산자와 연산자의 순서에 따라 값이 달라지기 때문에 두 개의 경우를 모두 구해줘야 한다.

 

❌ 첫번째 풀이

#include <iostream>
#include <set>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

int solution(int N, int number) {
	if (N == number) return 1;
	vector<vector<int>> dp(9);

	string s = to_string(N);
	dp[1].push_back(stoi(s));
	for(int i = 2; i <= 8; i++)
	{
		s += to_string(N);
		dp[i].push_back(stoi(s));

		for(int j = 0; j < dp[i-1].size(); j++)
		{
			dp[i].push_back(dp[i - 1][j] + N);
			dp[i].push_back(dp[i - 1][j] - N);
			dp[i].push_back(dp[i - 1][j] * N);
 			dp[i].push_back(dp[i - 1][j] / N);

			if (dp[i - 1][j] != 0)
			{
				dp[i].push_back(N - dp[i - 1][j]);
				dp[i].push_back(N / dp[i - 1][j]);
			}
		}

		unordered_set<int> temp(dp[i].begin(), dp[i].end());
		for(int t : temp)
		{
			if (t == number)
				return i;
		}
	}
	return -1;
}

int main()
{
	cout << solution(8, 53);
}

 

처음 문제를 풀때는, dp[1]과 dp[2], dp[3]에 각각 5, 55, 555의 숫자를 집어넣은 후, 이전 dp[i-1]의 원소들과 조합하여 사칙연산의 결과를 추가하였다.

뺄셈과 나눗셈은 역순의 계산 결과가 다르게 나오기 때문에 손수 한번 더 계산해주었다.

이후, 숫자 N을 i번 사용한 경우를 모두 추가했다면 그 중 number의 숫자와 같은 원소가 있는지를 검사하기 위해 unodered_set 배열에 원소들을 넣고 검사하였다.

 

그러나 위 풀이에선 두가지 문제점이 발생하였다.

 

1. DP = 5인 경우, DP 1 + DP 4일때, DP 2 + DP 3 일때, 등등 모든 경우를 비교해야 하는데 이전 DP로만 조합을 구했다.
2. vector로 조합 결과를 저장하여 중복값이 너무 많이 발생한다.
(아래에서 unordered_set으로 중복을 제거한 뒤 검사하긴 했지만, 한번에 중복을 제거하는 방법이 효율적이다)

 

따라서, 이러한 문제를 해결하기 위해 무려 4중 for문의 풀이를 작성하였다.

혼자 풀다가 3시간동안 못풀어서 다른분의 풀이를 보고 힘겹게 이해할 수 있었다...

 

⭕ 두번째 풀이

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int solution(int N, int number) {
	if (N == number) return 1;
	unordered_set<int> dp[8];

	string s = "";
	for(int i = 0; i < 8; i++)
	{
		s += to_string(N);
		dp[i].insert(stoi(s));
	}

	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 (b != 0)
						dp[i].insert(a / b);
				}
			}
		}
	}

	for(int i = 0; i < 8; i++)
	{
		if (dp[i].find(number) != dp[i].end())
			return i + 1;
	}
	return -1;
}

 

두번째 풀이는 vector를 사용했다가 unordered_set으로 중복을 제거하는것이 아니라, 처음부터 unordered_set으로 원소들을 추가하게끔 변경하였다.

 

핵심 풀이방법은 아래와 같다.

for문이 무려 4중으로 돌아가서 이해하는데 오래걸렸지만, 잘 이해하면 그렇게 어려운 내용은 아니다.

1. 숫자 N을 1번쓸때부터 최대 8번 쓸때까지의 N, NN, NNN,... 을 dp[i]에 초기화한다.
2. 처음 2중 for문은 dp끼리 서로 전부 비교하기 위해 필요한 for문이다. 
   예를 들어, dp[4]를 비교하는 차례라면, dp[0], dp[1], dp[2], dp[3]을 모두 dp[4]와 비교해야 하는 것
3. 안쪽 2중 for문은 dp의 모든 원소를 서로 비교하고 또 역순으로 비교하기 위함이다.
    dp[j]는 dp[i-j-1]과 원소내용을 하나하나 비교하게 된다. i-j-1가 j와 갖는 관계에 대해 그리고 왜 i-j-1을 사용하는지에 대해 이해하는데 시간이 좀 걸렸다.
예를들어, i = 4일때, j는 0부터 3까지 수행되고, 그로인해 dp[0]은 dp[3]과 / dp[1]은 dp[2]와 / dp[2]는 dp[1]과 / dp[3]은 dp[0]과 비교하며 역순까지 완벽하게 사칙연산을 수행하게 된다.
4. 나눗셈은 0으로 나누어지는 경우 에러를 발생하기 때문에 0으로 나누지 않도록 예외처리를 해준다.
5. 모든 사칙연산 경우를 dp에 추가했다면, N숫자를 1번사용하는 i = 0부터, 8번 사용하는 i = 7까지 for문을 돌리면서 number 값이 몇번째 i 에서 찾아지는지를 검사한다.

 

dp 문제는 역시나 너무너무 어렵고.. 점화식을 세우기까지가 정말 오래걸린 것 같다.

그리고 4중 for문을 상상치 못했다..

---

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

프로그래머스