취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7490번 문제인 0 만들기이다.

문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/7490 

1?2?3?4?5?6?7?8?9 형태의 문자열에서 "?" 위치에 +, - 또는 공백 중 하나씩 집어넣을 경우의 수는 3^8 = 6561가지이다. 따라서, 각 자연수 N에 대하여 모든 가능한 문자열을 만들어보고, 계산해보고, 값이 0이 나오는 문자열을 출력하는 것으로 문제를 해결할 수 있다.

모든 경우의 수를 생성하는 것은 재귀함수를 이용해서 간단히 구현할 수 있다.

테스트케이스들 사이에 빈 줄을 하나 출력해야 한다는 점에 유의하자.

아스키코드 순으로 공백이 + 또는 -보다 앞서서 온다는 점 또한 유의하자. (이는 문제에 제시된 예제를 통해서도 알 수 있다.)

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

string ans = "1";

void func(int digit, int a, int b, int end) {
	if (digit == end) {
		if (a + b == 0) cout << ans << '\n';
	}
	else {
		digit++;
		ans += " " + to_string(digit);
		func(digit, a, ((b > 0) ? b * 10 + digit : b * 10 - digit), end);
		ans.pop_back();
		ans.pop_back();
		ans += "+" + to_string(digit);
		func(digit, a + b, digit, end);
		ans.pop_back();
		ans.pop_back();
		ans += "-" + to_string(digit);
		func(digit, a + b, -digit, end);
		ans.pop_back();
		ans.pop_back();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		int N; cin >> N;
		func(1, 0, 1, N);
		cout << '\n';
	}
}