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

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

 

문제 설명

하나의 숫자와 사칙연산으로 특정 수를 만드려고 한다.

---

5와 사칙연산으로 12를 만드는 방법 중 일부이다.

12 = 5 + 5 + (5/5) + (5/5)
12 = 55/5 + 5/5
12 = (55+5) / 5

---

위에서 볼 수 있듯이, 하나의 숫자 N으로 목표하는 숫자 number를 만드는 방법은 여러 가지가 있을 수 있다.
그리고 각각 사용한 숫자의 수는 6,5,4개이며, 최솟값은 4이다.

사용할 숫자 N과 만들어야 할 숫자 number가 주어졌을 때, N의 사용횟수의 최솟값을 리턴하자.

 

제한 사항

• 1 <= N <= 9
• 1 <= number <= 32,000
• 수식은 사칙연산과 괄호연산만 사용가능하다.
  • 나누기에서 나머지는 무시한다.
• 최솟값이 8보다 크면 -1을 리턴한다.

 

1. DP - O(4^N)

문제를 읽고 느낌이 잘 오지 않는다면, 일단 예시들을 이해해보자.

예시로 주어진 N=2, number=11에 대해 확인을 해 보도록 하자.

---

2를 1개 써서 만들 수 있는 숫자는 무엇이 있을까?
2 하나 뿐이다. 사칙연산은 최소한 하나의 숫자가 더 필요하다.
숫자 하나로는 3을 만들 수 없다. 숫자를 하나 더 넣어보자.

 

2를 2개 써서 만들 수 있는 숫자는 무엇이 있을까?
사칙연산을 쓰지 않고 만들 수 있는 수로는 22가 있다.

2를 1개 써서 만들 수 있는 수 들과 2를 1개 써서 만들 수 있는 수 들로 각각 사칙연산을 한 결과를 모으면, 이것도 2를 2개 써서 만들 수 있는 수들의 모임이 된다.

22, 2+2, 2-2, 2x2, 2/2

실제로 계산한 값을 넣어도 되지만, 여기서는 수식으로만 남겨두자.
여기의 결과 중에는 3이 없다. 숫자를 하나 더 넣어봐야 한다.

 

그럼 2를 3개 써서 만들 수 있는 숫자는 무엇이 있을까?
사칙연산을 쓰지 않고 만들 수 있는 수로는 222가 있다.

2를 1개 써서 만들 수 있는 수 들과 2를 2개 써서 만들 수 있는 수 들로 각각 사칙연산을 한 결과를 모아보자.

2 + (22), 2 + (2 + 2), 2 + (2 - 2), 2 + (2 x 2), 2 + (2 / 2),
2 - (22), 2 - (2 + 2), 2 - (2 - 2), 2 - (2 x 2), 2 - (2 / 2),
2 x (22), 2 x (2 + 2), 2 x (2 - 2), 2 x (2 x 2), 2 x (2 / 2),
2 / (22), 2 / (2 + 2), 2 / (2 - 2), 2 / (2 x 2), 2 / (2 / 2)

갑자기 연산 결과들이 급격하게 늘어났다. 그리고 위의 결과 중 다음 항목을 제거하자. 0으로 나누기는 제외해야 한다.

2 / (2 - 2)

하지만 여기서 끝이 아니다.

2를 2개 써서 만들 수 있는 수 들과 2를 1개 써서 만들 수 있는 수도 봐야한다.
덧셈과 곱셈은 교환법칙이 성립하지만, 뺄셈과 나눗셈은 교환법칙이 성립하지 않는다.

22 + 2, 22 - 2, 22 x 2, 22 / 2
(2 + 2) + 2, (2 + 2) - 2, (2 + 2) x 2, (2 + 2) / 2
(2 - 2) + 2, (2 - 2) - 2, (2 - 2) x 2, (2 - 2) / 2
(2 x 2) + 2, (2 x 2) - 2, (2 x 2) x 2, (2 x 2) / 2
(2 / 2) + 2, (2 / 2) - 2, (2 / 2) x 2, (2 / 2) / 2

그리고 위의 결과 중, 다음 식으로 11을 만들 수 있다.

22 / 2

숫자 2를 3개 사용해서 3을 만들었다.
따라서 N=2, number=11의 답은 3이다.

---

 

위의 과정을 일반화하면 다음과 같다.

숫자 N을 i개의 숫자를 써서 만들 수 있는 수들을 찾는다.

먼저, 사칙연산 없이 N만 나열한 수, NNNNN...을 만든다.

1개의 수로 만들 수 있는 숫자와 i-1개의 숫자로 만들 수 있는 모든 숫자들의 조합애 대해 사칙연산을 수행한다.
2개의 수로 만들 수 있는 숫자와 i-2개의 숫자로 만들 수 있는 모든 숫자들의 조합애 대해 사칙연산을 수행한다.
… i-1개의 수로 만들 수 있는 숫자와 1개의 숫자로 만들 수 있는 모든 숫자들의 조합애 대해 사칙연산을 수행한다.

만약 위의 계산결과중에 number가 있으면 i가 답이다.
없으면 i+1번을 써서 만들 수 있는 숫자를 찿아본다.
만약 i가 9가 되었다면, -1을 리턴한다.

물론 위의 과정처럼 1 x (i-1), 2 x (i-2), … , (i-1) x 1 이런 식으로 모두 순회할 필요는 없다. 절반정도만 수행하되, 1 x (i-1)에 대해 연산할 때 교환 법칙이 성립하지 않는 뺄셈과 나눗셈에 대해 자리를 바꿔서 한 번 더 수행해주면 연산량을 좀 더 줄일 수 있다.

위의 과정에서 0으로 나누는 일이 없도록 주의하자.

 

숫자 i개로 만들 수 있는 모든 숫자들을 기억하고, 이를 i+1개의 숫자로 만들 수 있는 경우의 수를 구할 때 사용한다. 즉, 이 전에 계산한 결과들을 재활용하여 새로운 해를 구하는데 사용하므로, 이 과정 또한 동적 계획법을 사용한다고 할 수 있다.

 

위의 과정에서, 비록 다른 연산을 사용했지만 결과는 같은 결과가 나올 수도 있다.
(2 x 2) / 2 는 2고, (2 + 2) - 2도 2다.

연산 결과를 배열등에 보관을 한다면, 중복된 결과에 대해 한번 더 연산을 수행하게 된다. 따라서, 중복된 원소를 허용하지 않는 자료구조에 결과를 담는 것이 좋을 것이다. 여기서는 저장되는 순서는 중요하지 않기 때문에, unordered_set에 저장한다.

Python이라면 set, Java라면 HashSet을 사용하면 좋을 것이다.

 

그러면 위의 내용을 코드로 표현해보자.

 

solution.cpp

#include <vector>
#include <unordered_set>

using namespace std;

int solution(int N, int number) {
	unordered_set<int> p[8];
    
    int v = 0;
	for (int i = 0; i < 8; ++i)
	{
		v = 10 * v + N;
		p[i].insert(v);
		for (int j = 0; j < i; ++j)
		{
			int k = i - j - 1;
			for (auto it1 = p[j].begin(); it1 != p[j].end(); ++it1)
			{
				for (auto it2 = p[k].begin(); it2 != p[k].end(); ++it2)
				{
					p[i].insert(*it1 + *it2);
					p[i].insert(*it1 - *it2);
					p[i].insert((*it1) * (*it2));
					if (*it2 != 0)	p[i].insert((*it1) / (*it2));
				}
			}

			auto it = p[i].find(number);
			if (it != p[i].end())   return i + 1;
		}
	}

	return -1;
}