[G5] 백준 7490번 0 만들기 C++ 백트래킹, 브루트포스 알고리즘, 구현, 문자열

리뷰

 

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

어렵진 않은데 공백이라는 조건 때문에 생각해야 하는 케이스가 많아서 구현에 시간이 좀 걸리는 문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N에서 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하여 수식을 만들고, 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 되는 케이스를 문자열로 출력해야 한다.

 

 

전역 변수

• t, n : 테스트 케이스의 개수 t, 각 테스트 케이스 마다 주어지는 수열의 길이 n
• ans : 정답을 저장할 문자열 벡터
• char : +, -, 공백등의 연산자를 저장할 문자형 벡터

 

함수

1. calc

int calc()

 

입력 받은 연산자를 토대로 계산을 하여 나온 결과값을 리턴하는 함수

1. 1의 경우 무조건 처음에 나타나니 정수형 벡터 nums에 1을 넣은채로 초기화 해준다.
2. 2 ~ n의 수를 nums벡터에 추가해 주어야 한다, 다만 사이 사이에 존재하는 연산자를 먼저 체크해 준다.
3. for문을 2부터 시작했으니 우선 ops[i - 2]가 공백인 경우만 먼저 체크하여 nums벡터를 완성한다.
4. 만약 공백이라면 nums의 맨 뒤 숫자를 빼내고 10을 곱한 값에 i를 더해준 값을 다시 push해준다.
5. 공백이 아니라면 그냥 i를 nums벡터에 추가해 주면 된다.
6. sum을 nums의 가장 앞 원소로 초기화 해주고, 인덱스를 1로 초기화 해준다.
7. ops배열을 순회하며 만약 +라면 sum에 nums의 idx원소를 더해주고 idx를 증가시킨다.
8. 만약 -라면 sum에 nums의 idx원소를 빼주고 idx를 증가시킨다.
9. 만약 공백이라면 이미 전처리를 마쳤으니 아무 것도 하지 않아도 된다.
10. 모든 작업을 마친 뒤 sum을 return해준다.

 

2. bt

void bt(int level)

 

백트래킹을 통해 연산 결과가 0이 되는 케이스를 모두 찾는 함수

1. 매개변수로 재귀 단계인 level을 받는다, 초기 단계는 1부터 시작한다.
2. 연산자의 개수는 n - 1개이고, 1부터 시작했으니 기저 조건은 level이 n에 도달했을 때이다.
3. calc함수를 통해 연산을 마친 값이 0이라면 문자열을 제작해 주어야 한다.
4. temp를 "1"로 초기화 하고, 사이 사이에 연산자와 다음 숫자를 추가해 주면 된다.
5. 문자열이 완성되었다면 ans배열에 추가해 주고 return해준다.
6. 기저조건에 도달하지 못했다면 +, -, 공백 연산을 재귀를 통해 모두 진행해 준다.

 

문제풀이

1. 테스트 케이스의 개수 t를 입력 받고, t번의 반복문을 실행해 준다.
2. n을 입력 받고, 이전 테스트 케이스에서 사용한 ans, ops를 clear처리해 준다.
3. bt함수를 매개변수 1을 전달하여 수행해 준다.
4. 완성된 ans벡터를 오름차순으로 정렬 해준다.
5. ans에 저장된 문자열을 줄바꿈을 기준으로 출력해 준다.
6. 모든 출력이완료되었다면 줄바꿈을 한번 더 실행해 준다.
7. 위 작업을 매 테스트 케이스마다 수행해 준다.

 

참고 사항

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다.

각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int t, n;
vector<string> ans;
vector<char> ops;

int calc() {
	vector<int> nums(1, 1);
	for (int i = 2; i <= n; i++) {
		if (ops[i - 2] == ' ') {
			int temp = nums.back();
			nums.pop_back();
			nums.push_back(temp * 10 + i);
		}
		else nums.push_back(i);
	}

	int sum = nums[0];
	int idx = 1;
	for (int i = 0; i < n - 1; i++) {
		if (ops[i] == '+') sum += nums[idx++];
		else if (ops[i] == '-') sum -= nums[idx++];
	}
	return sum;
}

void bt(int level) {
	if (level == n) {
		if (!calc()) {
			string temp = "1";
			for (int i = 0; i < n - 1; i++) {
				temp += ops[i];
				temp += i + '2';
			}
			ans.push_back(temp);
		}
		return;
	}

	ops.push_back('+');
	bt(level + 1);
	ops.pop_back();

	ops.push_back('-');
	bt(level + 1);
	ops.pop_back();

	ops.push_back(' ');
	bt(level + 1);
	ops.pop_back();
}

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

	cin >> t;
	while (t--) {
		cin >> n;
		ans.clear();
		ops.clear();
		bt(1);
		sort(ans.begin(), ans.end());
		for (const string& s : ans) cout << s << "\n";
		cout << "\n";
	}
}