[백준/BOJ] 백준 1248번 : 맞춰봐

www.acmicpc.net/problem/1248

1248번: 맞춰봐

입력되는 문자열을 s에 직각 삼각형 형태로 저장한 뒤, Solve에서 selected에 수를 넣어가며 index번째 수가 적합한지 확인한다. 고른 index번째 수가 적합한지 확인할 때 직각삼각형 형태의 s배열의 해당 index열을 확인하는데 index행부터 0행까지 확인하며 적합한지 판단한다.

 

코드

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

int n;
vector<int> number;
string input;
vector<vector<char>> s(10, vector<char>(10, ' '));

//selected에 index번째가 적합한지 체크
bool Check(int index, vector<int>& selected)
{
	int sum = 0;

	//직각삼각형 형태의 s배열의 해당 index열을 확인하는데 index행부터 0행까지 확인한다 
	for (int i = index; i >= 0; i--)
	{
		sum += selected[i];

		if (s[i][index] == '-' && sum >= 0)
			return false;

		if (s[i][index] == '+' && sum <= 0)
			return false;

		if (s[i][index] == '0' && sum != 0)
			return false;
	}

	return true;
}

bool Solve(int index, vector<int>& selected)
{
	//n개를 다 골랐을때
	if (selected.size() == n)
		return true;

	for (int i = 0; i < number.size(); i++)
	{
		selected.push_back(number[i]);

		if (Check(index, selected) == true)
		{
			if (Solve(index + 1, selected) == true)
				return true;
		}

		selected.pop_back();
	}

	return false;
}

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

	//-10~10 숫자를 저장한다
	for (int i = -10; i <= 10; i++)
		number.push_back(i);

	cin >> n;
	cin >> input;

	int index = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			s[i][j] = input[index]; //직각 삼각형 형태로 s배열을 채운다
			index++;
		}
	}

	vector<int> selected;
	Solve(0, selected);

	for (int i = 0; i < selected.size(); i++)
		cout << selected[i] << " ";

	return 0;
}