[BOJ] 1248 맞춰봐

문제: https://www.acmicpc.net/problem/1248

 

문제 풀이:

 

각 값들을 행렬로 표현하면 다음과 같다.

대각선은 자기 자신을 나타낸다. 즉, arr[idx][idx]의 부호는 $n_{idx}$의 부호이다.

	$n_{1}$	$n_{2}$	$n_{3}$	$n_{4}$
$n_{1}$	n1	n1+n2	n1+n2+n3	n1+n2+n3+n4
$n_{2}$		n2	n2+n3	n2+n3+n4
$n_{3}$			n3	n3+n4
$n_{4}$				n4

- 해당 숫자의 부호가 음수이면, 가능한 값은 [-10,1]

- 해당 숫자의 부호가 양수이면, 가능한 값은 [1,10]

- 해당 숫자의 부호가 0이면, 가능한 값은 '0'

 

이렇게 범위를 좁혀 문제를 풀 수 있다. 

 

모든 경우의 수를 구하는 것이 아니라, 적당한 값들을 찾으면 바로 리턴해주기 때문에 시간 초과가 나지 않는다.

 

<함수 설명>

bool check(int sum, int pos) {

	for (int i = 0; i < pos; i++) {
		if (arr[i][pos] == '+') {
			if (sum <= 0) return false;
		}
		else if (arr[i][pos] == '-') {
			if (sum >= 0) return false;
		}
		else {
			if (sum != 0) return false;
		}
		sum -= num[i];
	}
	return true;
}

num[idx]: 정답이라 예상하는 값들을 넣어 놓는 변수

pos: 현재 넣은 값의 index 번호 ($n_{pos}$)

sum: num[0]+num[1]+..+num[pos]

 

예를 들어, $n_{3}$의 값을 넣고 check 함수로 적절한 값인지 확인한다고 하자.

	$n_{1}$	$n_{2}$	$n_{3}$	$n_{4}$
$n_{1}$	n1	n1+n2	n1+n2+n3	n1+n2+n3+n4
$n_{2}$		n2	n2+n3	n2+n3+n4
$n_{3}$			n3	n3+n4
$n_{4}$				n4

3은 주황색 부분과만 연관 있으므로, sum에서 앞에 값 하나씩 빼주면서 적절한 값인지 판단하면 된다.

 

 

전체 소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>

using namespace std;


char arr[11][11];
int num[11], n;

bool check(int sum, int pos) {  // num[idx]에 넣은 값이 적절한지 확인

	for (int i = 0; i < pos; i++) {
		if (arr[i][pos] == '+') {
			if (sum <= 0) return false;
		}
		else if (arr[i][pos] == '-') {
			if (sum >= 0) return false;
		}
		else {
			if (sum != 0) return false;
		}
		sum -= num[i];
	}
	return true;
}
bool func(int sum,int idx) {

	if (idx == n) {
		return true;
	}
	if (arr[idx][idx]=='+') {
		for (int i = 1; i <= 10; i++) {
			num[idx] = i;
			if (check(sum+i, idx)) {
				if (func(sum + i, idx + 1)) return true;
			}
		}
		return false;
	}
	else if (arr[idx][idx] == '-') {
		for (int i = -10; i <0; i++) {
			num[idx] = i;
			if (check(sum + i, idx)) {
				if (func(sum + i, idx + 1)) return true;
			}
		}
		return false;
	}
	else {
		num[idx] = 0;
		return func(sum, idx + 1);
	}
	return true;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	func(0, 0);
	
	for (int i = 0; i < n; i++) {
		cout << num[i] << " ";
	}
	
	return 0;
}