[C++] 백준 13140번: Hello World!

문제 링크

13140번: Hello World!

문제 요약

hello + world = N을 만족하도록 만들어야 한다. 각 자리에는 0 ~ 9까지의 서로 다른 수가 들어올 수 있고, 이 중 h와 w는 0이 될 수 없다.

접근 방법

간단한 완전탐색 문제라고 생각할 수 있습니다. 0 ~ 9까지 서로 다른 수를 가지도록 구현만 해주면 되는 문제인데, 출력 형식이 조금 까다로운 편입니다.

백트래킹으로 구현을 해도 되고, C++의 경우 next_permutation을 사용하면 더 간단하게 구현을 할 수 있습니다.

테스트케이스만 보고 출력 형식을 작성하는 경우, N의 앞에 공백을 2개 넣는 실수를 할 수 있습니다. 하지만 N이 10만 이상이라면 공백이 하나 들어가야 AC를 받을 수 있습니다. 제 경우에도 이런 실수를 해서, 애먼 로직만 검사를 하고 있었습니다.

링크

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 101

using namespace std;

int n, hello[5] = { 2, 1, 3, 3, 4 }, world[5] = { 6, 4, 5, 3, 0 }, arr[7];
bool visited[10];

void print(void)
{
	cout << "  ";
	for (int i = 0; i < 5; i++)
		cout << arr[hello[i]];
	cout << "\n+ ";
	for (int i = 0; i < 5; i++)
		cout << arr[world[i]];
	cout << "\n-------\n" << (n > 100000 ? " " : "  ") << n << endl;
}

void func(int idx)
{
	if (idx == 7)
	{
		if (!arr[2] || !arr[6])
			return;

		int sum = 0;
		for (int i = 0; i < 5; i++)
			sum += arr[hello[i]] * pow(10, 4 - i);
		for (int i = 0; i < 5; i++)
			sum += arr[world[i]] * pow(10, 4 - i);

		if (sum == n)
		{
			print();
			exit(0);
		}

		return;
	}

	for (int i = 0; i < 10; i++)
	{
		if (!visited[i])
		{
			arr[idx] = i;
			visited[i] = true;
			func(idx + 1);
			visited[i] = false;
		}
	}
}

int main(void)
{
	FASTIO;
	cin >> n;

	func(0);
	cout << "No Answer\n";
	return 0;
}