백준 2287: 모노디지털 표현

문제 요약

몇 개의 숫자 K(K는 1, 2, …, 9중 하나)와 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)만을 사용하여 어떤 자연수 X를 수식으로 표현한 것을 X의 K-표현이라 부른다. 수식에는 괄호가 포함될 수 있으며, 나눗셈은 나눈 몫만을 취한다.

예를 들어 12의 5-표현을 몇 개 써 보면 5+5+(5/5)+(5/5), 55/5+5/5, (55+5)/5 등이 있다. K-표현의 길이를 사용한 K의 개수라 하면, 각각의 길이는 6, 5, 4가 된다.

K가 주어졌을 때, 어떤 자연수의 K-표현 중 가장 짧은 길이를 알아보려 한다.

문제 분류

• 다이나믹 프로그래밍
• 자료 구조
• 해시를 사용한 집합과 맵
• 트리를 사용한 집합과 맵

문제 풀이

숫자 k를 사용하는 갯수에 따른 DP문제이다. 예를들어, 숫자 k를 4번 사용하여 만드는 식은 3/1, 2/2, 1/3의 경우로 나누어 생각할 수 있다. 여기서 분자와 분모에 사용한 숫자의 개수의 합이 k가 된다. 즉, k를 n번 사용하여 나타낼 경우 그 경우는 1/n-1, 2/n-2, ... , n-1/1의 경우를 모두 합한 것이 될 것이다. 이것을 기반으로 점화식을 세우면 된다.

일반적인 DP문제와 달리 set<int>를 반환하는 DP가 되겠다. s[8]을 선언하여 각 1번~8번 사용했을 경우의 나타나는 수의 집합을 만들었다. sol(int n)에서는 우선 n에 따라 연속된 k의 수를 삽입한 후, (0이면 k, 1이면 k*10 + k..) 만들수 있는 수의 조합으로 사칙연산을 수행하였다. 이때 혹시 몰라서 음수의 경우도 모두 포함시켜주었다. 범위기반 for문의 경우 sol(i)를 for안에 직접 넣어서 수행시켰다. 그렇게 s[n]을 구축하면서, 해당 set안에 사용자가 입력한 값이 있는지 탐색하며, 그 결과에 따라 알맞은 값을 출력하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int k;
set<int> s[8];

set<int>& sol(int n) {
	if (!s[n].empty()) return s[n];
	int temp = k, i = n;
	while (i--) {
		temp *= 10;
		temp += k;
	}
	s[n].insert(temp);
	s[n].insert(-temp);
	for (int i = 0; i < n; i++) {
		for (auto& it : sol(i)) {
			for (auto& it2 : sol(n - i - 1)) {
				s[n].insert(it + it2);
				s[n].insert(-it - it2);
				s[n].insert(it - it2);
				s[n].insert(it2 - it);
				s[n].insert(it * it2);
				if (it2 != 0) {
					s[n].insert(it / it2);
					s[n].insert(-(it / it2));
				}
				if (it != 0) {
					s[n].insert(it2 / it);
					s[n].insert(-(it2 / it));
				}
			}
		}
	}
	return s[n];
}

int main()
{
	int t, n;
	scanf("%d%d", &k, &t);
	while (t--) {
		bool d = false;
		scanf("%d", &n);
		for (int i = 0; i < 8; i++) {
			if (sol(i).find(n) != sol(i).end()) {
				printf("%d\n", i + 1);
				d = true;
				break;
			}
		}
		if (!d) printf("NO\n");
	}
	return 0;
}