[C++] 백준 2287번: 모노디지털 표현

문제 링크

2287번: 모노디지털 표현

문제 요약

K를 여러 개 이용하거나 사칙연산을 이용해 자연수 X를 수식으로 나타낸 것을 X의 K-표현이라고 한다. 입력 N이 주어지면, N의 가장 짧은 K 표현의 길이를 구해야 한다. 단, 길이가 8을 넘어가면 NO를 출력한다.

접근 방법

처음에는 길이를 1씩 늘려가는 식으로 접근했다가 틀렸습니다. 길이가 1인 표현으로 2인 표현을 만들고, 2인 표현으로 3인 표현을 만들고... 이런식으로 반복을 했었는데, 한 번 틀리고 나서 실수를 바로 알아차리고 고쳤습니다. 길이가 5인 K-표현은 2인 표현과 3인 표현 사이의 연산으로도 나타낼 수 있는데 이것이 배제된 생각을 하고 있었습니다.

틀린 코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int k, n;
	cin >> k >> n;

	while (n--) {
		int a;
		cin >> a;

		unordered_set<int> s;
		s.insert(k);

		if (a == k) {
			cout << 1 << '\n';
			continue;
		}

		string tmp;
		tmp.push_back(k + '0');
		for (int i = 1; i <= 8; i++) {
			vector<int> v;
			bool flag = false;
			for (auto& j : s) {
				if (j == a) {
					flag = true;
					break;
				}
			}

			if (flag) {
				cout << i << '\n';
				break;
			}

			if (i == 8) {
				cout << "NO\n";
				break;
			}

			for (auto& j : s) {
				if (s.find(j + k) == s.end())
					v.push_back(j + k);
				if (s.find(j - k) == s.end())
					v.push_back(j - k);
				if (s.find(j * k) == s.end())
					v.push_back(j * k);
				if (s.find(j / k) == s.end())
					v.push_back(j / k);
			}

			for (auto& j : v)
				s.insert(j);

			tmp.push_back(k + '0');
			s.insert(stoi(tmp));
		}
	}

	return 0;
}

길이가 2인 표현은 길이가 1인 표현 둘의 연산으로 구할 수 있습니다.
길이가 3인 표현은 길이가 1인 표현과 2인 표현의 연산으로 구할 수 있습니다.
4인 표현은 1/3, 2/2를 통해 구할 수 있습니다.
길이가 5, 6, 7, 8인 표현도 마찬가지입니다.

이를 이용해서 코드를 작성해주면 됩니다. 길이가 L인 표현을 구하기 위해서는 합이 L이 되는 두 표현을 이용해주면 됩니다.

중간 과정에서 나올 수 있는 수의 범위가 넓기 때문에 unordered_set을 사용해주었습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int k, n;
	cin >> k >> n;

	while (n--) {
		int a;
		cin >> a;

		if (a == k) {
			cout << 1 << '\n';
			continue;
		}

		unordered_set<int> s[10];

		string tmp;
		for (int i = 1; i <= 8; i++) {
			tmp.push_back(k + '0');
			s[i].insert(stoi(tmp));
		}

		for (int i = 2; i <= 8; i++) {
			for (int j = 1; j <= i - 1; j++) {
				for (auto& k : s[j]) {
					for (auto& l : s[i - j]) {
						s[i].insert(k + l);
						s[i].insert(k - l);
						s[i].insert(k * l);
						if(l != 0) s[i].insert(k / l);
					}
				}
			}

			bool flag = false;
			for (auto& j : s[i]) {
				if (j == a) {
					cout << i << '\n';
					flag = true;
					break;
				}
			}

			if (flag)
				break;

			if (i == 8)
				cout << "NO\n";
		}
	}

	return 0;
}