[C++] 백준 1248번: 맞춰봐

문제 링크

1248번: 맞춰봐

문제 요약

-10 ~ 10까지의 정수를 N개 나열한다. 그리고 해당 수열의 모든 구간합이 양수, 음수, 0 중에 어떤 것인지가 주어진다. 이때, 조건을 만족하는 N개의 수로 이루어진 수열을 하나 출력해야 한다.

접근 방법

-10 ~ 10까지의 숫자를 넣으면서 백트래킹을 돌리면 됩니다. 중요한 점은, 수가 중복이 가능하다는 점입니다. 중복이 안 될거라고 생각하고 접근해서 읽고 푸는데 50분이나 걸렸습니다.

입력 받은 +, -, 0으로 이루어진 문자열을 잘 처리해서, 구간을 나타내도록 변형하는 것도 중요합니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n;
char mat[11][11];
string str;
vector<int> v;

bool check(int cnt)
{
	for (int i = 0; i < v.size(); i++)
	{
		int sum = 0;
		for (int j = i; j < v.size(); j++)
		{
			sum += v[j];

			if (sum == 0 && mat[i][j] != '0')
				return false;
			if (sum > 0 && mat[i][j] != '+')
				return false;
			if (sum < 0 && mat[i][j] != '-')
				return false;
		}
	}

	return true;
}

void func(int cnt)
{
	if (cnt == n)
	{
		for (int i = 0; i < v.size(); i++)
			cout << v[i] << ' ';
		exit(0);
	}

	for (int i = -10; i <= 10; i++)
	{
		v.push_back(i);
		if (check(cnt))
			func(cnt + 1);
		v.pop_back();
	}
}

int main(void)
{
	cin >> n >> str;

	int idx = 0;
	for (int i = 0; i < n; i++)
		for (int j = i; j < n; j++)
			mat[i][j] = str[idx++];
	func(0);
}