[백트래킹] 1248 맞춰봐

맞춰봐 (1248)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 1248 맞춰봐!

int n;
// input +- 를 1 -1 로 치환하여 담음
int sign[10][10];
// 정답이 될 수열
int ans[10];

bool check(int index){
	int sum = 0;
	for(int i = index; i >= 0; i--){
		sum += ans[i];
		if (sign[i][index] == 0) {
			if (sum != 0) return false;
		} else if (sign[i][index] < 0) {
			if (sum >= 0) return false;
		} else if (sign[i][index] > 0) {
			if (sum <= 0) return false;
		}
	}
	return true;
}

bool go(int index){
	// 기저사례 : index 가 n 이 되면 true
	if(index == n){
		return true;
	}
	
	// sign[index][index] 가 0 이라면 해당 값도 0이어야 함
	if(sign[index][index] == 0){
		ans[index] = 0;
		// index 까지의 합을 이용해서 sign 과 비교 && 다음 index
		return check(index) && go(index + 1);
	}
	
	for(int i = 1; i <= 10; i++){
		ans[index] = sign[index][index] * i;
		if(check(index) && go(index + 1)) return true;
	}
	return false;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n;
	string s;
	cin >> s;
	
	// sign 에 -1 1 0 으로 치환하여 저장
	int cnt = 0;
	for(int i=0; i < n; i++){
		for(int j = i; j < n; j++){
			if(s[cnt] == '0'){
				sign[i][j] = 0;
			} else if(s[cnt] == '+'){
				sign[i][j] = 1;
			} else{
				sign[i][j] = -1;
			}
			cnt += 1;
		}
	}
	
	go(0);
	
	for (int i=0; i<n; i++) {
 		cout << ans[i] << ' ';
 	}
	cout << '\n';
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 경우의 수를 계산해보자.

- 21^10 이므로 그냥 브루트포스만으로는 시간초과가 나올것을 염두에 두어야 한다.

2. 브루트 포스를 구현해보자.

- N과 M (3) 문제 처럼 -10 ~ 10 까지의 수를 중복 허용하여 10자리에 넣는 것이다.

3. 백트래킹 조건을 추가하여 시간을 줄여보자.

3-1. [i][j] 까지의 합이 있을 때, [i][i] 를 집중해서 보자. [i][i] 가 0이라면 해당 수는 0. 음수라면 음수이다.

3-2. 브루트 포스처럼, 완성된 배열을 만들고 검사하는 것이 아니라 하나의 수를 넣을 때 input 인 +-0 을 검사해보자.

이것은 check 함수에 반영되어 있다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점