[BOJ/C++] 7490 0 만들기

문제

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

풀이

이 문제는 풀이 방식이 떠오르지 않았다. 다른 사람 풀이 참고해도 이해하는데 한참 걸렸다. 재귀가 조금 취약한 듯..
보통 테스트케이스로 로직에 따라 결과 예측한 뒤에 코드를 작성하는데 재귀는 그 과정이 끝도 없어서 어느정도 생각하고 코드를 작성해야 해서 그런 듯하다.
재귀 방식 익숙해지자 !!

1부터 입력 받은 수까지 증가시키며 + - 공백 각각의 경우에 대해 재귀를 호출하고, 마지막에 식을 계산해서 0이 되는지 확인한다.

재귀함수 인자만 잘 설정해주면 코드 자체는 엄청 간결하다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

vector<string> ans;

void solve(int target, int sum, int sign, int prev, int idx, string expression) {
	if (idx == target) {
		sum += (prev * sign);

		if (sum == 0)
			ans.push_back(expression);
		return;
	}
	else {
		// +
		solve(target, sum + (prev * sign), 1, idx + 1, idx + 1, expression + '+' + to_string(idx + 1));

		// -
		solve(target, sum + (prev * sign), -1, idx + 1, idx + 1, expression + '-' + to_string(idx + 1));

		// 공백으로 계산
		solve(target, sum, sign, prev * 10 + (idx + 1), idx + 1, expression + ' ' + to_string(idx + 1));
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;
	while (T--) {
		int num;
		cin >> num;
		solve(num, 0, 1, 1, 1, "1");
		sort(ans.begin(), ans.end());

		for (int i = 0; i < ans.size(); i++) {
			cout << ans[i] << "\n";
		}
		cout << '\n';
		ans.clear();
	}

	return 0;
}