백준 1248번 맞춰봐 문제 해설, 백트레킹 개념 다지기

백준 1248번 맞춰봐 문제 해설

문제 링크

solved.ac 기준 골드 3 난이도의 문제입니다. 백트래킹 을 사용하여 문제를 해결하였습니다.

백트래킹 개념 다지기에 좋은 문제 였습니다.

문제

규현이는 종이에 수를 N개 썼다. 
(규현이가 아는 가장 큰 수는 10이기 때문에, 수를 10개까지만 쓸 수 있다.) 
그 다음에, 가능한 모든 N*(N+1)/2개의 구간의 합을 구했다. 이 것을 해인이는 행렬로 표현했다.

규현이가 쓴 수를 A라고 하면, A[i]는 규현이가 i번째 쓴 수이다. 그리고, S[i][j]는 A[i]부터 A[j]까지 
합이 0보다 크면 +, 0이면 0, 0보다 작으면 -이다. 여기서 i는 항상 j보다 작거나 같다. 
이렇게 배열을 채우면 배열에는 총 N*(N+1)/2개의 문자가 있다. 
(+, -, 0 중 하나) 이 S 배열이 주어졌을 때, 규현이가 쓴 N개의 수 A를 구해서 출력하면 된다. 
규현이는 -10부터 10까지의 정수밖에 모르기 때문에, 
A도 -10부터 10까지의 정수로만 이루어져 있어야 한다.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 
둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 
첫 번째 줄에 해당하고, 다음 N-1개의 문자는 두 번째 줄에 해당한다. 
마찬가지로 마지막 문자는 N번째 줄에 해당하는 문자다.

출력

첫째 줄에 수열의 원소 N개를 빈 칸을 사이에 두고 출력한다. 
답이 여러 가지 일 경우에는 아무거나 출력하면 된다.

예제입력

4
-+0++++--+

예제출력

-2 5 -3 1

문제 풀이

문제의 입력인 -+0++++–+ 가 문제의 시작부터 우리를 헷갈리게 만드네요.

문제의 정의대로 그림으로 한번 표현해 봅시다.

문제에서 주어진 조건대로, S [i] [j]는 A[i]부터 A[j]까지 합이 0보다 크면 +, 0이면 0, 0보다 작으면 -이다. 를 한줄의 문자열이 아닌 i, j 위치에 2차원 배열로 나타내 봤습니다.

이제야 좀 이해가 되네요! 이제 문제에서 주어진 출력인 -2 5 -3 1 이 위의 조건을 어떤 방식으로 만족하는지 살펴보겠습니다.

-2 5 -3 1 의 맨 앞부터 순서대로 살펴보겠습니다. -2 는 문제의 주어진 조건대로 S [0] [0] 의 부호인 - 를 만족하네요. 다음 숫자로 넘어가 보겠습니다.

5는 어떨까요? 2번째 숫자이므로 S [1] [1] 의 부호를 5가 만족해야 하며, 첫번째 숫자인 -2 와 두번째 숫자인 5 의 합이 S [0] [1] 의 부호를 만족해야 합니다. 문제의 주어진 조건을 2차원 배열로 풀어서 직접 보니 더 직관적이지 않나요? 다음 숫자를 보겠습니다.

세번째 숫자인 -3 의 경우입니다. -3 은 S [2] [2] 의 부호를, 두번째 숫자와 세번째 숫자의 합인 (5 - 3) 은 S [1] [2] 의 부호를, 첫번째, 두번째, 세번째 숫자의 합인 (-2 + 5 -3) 은 S [0] [2] 의 부호를 만족하는 것을 알 수 있습니다. 이제야 좀 규칙이 보이네요!

지금까지 살펴본 과정들을 토대로 규칙을 유도해 보겠습니다. N 번째 숫자는 S [N] [N] 의 부호를 만족하며, N번째 숫자 + N-1 번째 숫자는 S [N] [N-1] 의 부호를 만족합니다. N번째 숫자부터 X번째 숫자 (X = 1, … , N-1) 까지의 합이 모두 각각의 S [N] [X] 행렬의 부호를 만족하면, N번째 숫자는 사용할 수 있겠네요!

N번째 숫자가 만족해야 하는 조건들을 알았으니, 이를 그대로 코드로 옮기면 되겠네요.

이때, N번째 숫자는 -10 ~ 10 사이의 정수가 가능하므로, DFS 로 각 N번째 마다 가능한 모든 경우를 탐색해보겠습니다.

소스코드

#include<iostream>
#include <queue>
#include <vector>

using namespace std;

char map[11][11];
int num;
vector<int> v;

bool possible(int idx)
{
	int sum = 0;

	for (int i = idx; i >= 0; i--)
	{
		// V[idx] 부터 V[i] 까지의 합
		sum += v[i];

		// V[idx] 부터 V[i] 까지의 합은 map[i][idx] 의 부호를 만족해야 한다
		if (map[i][idx] == '+' && sum <= 0)	return false;
		if (map[i][idx] == '-' && sum >= 0)	return false;
		if (map[i][idx] == '0' && sum != 0)	return false;
	}
	return true;
}

void solve(int idx)
{
	// 모든 조건을 만족하는 경우
	if (idx == num)
	{
		for (int i = 0; i < v.size(); i++)
			cout << v[i] << " ";
		exit(0);
	}

	// -10 부터 10 까지
	for (int i = -10; i <= 10; i++)
	{
		v.push_back(i);

		// idx 번째의 숫자가 모든 조건을 만족한다면 idx+1번째로 진행
		if (possible(idx))
			solve(idx + 1);

		v.pop_back();
	}
}

int main(void)
{
	cin >> num;
	string s;
	cin >> s;

	int idx = 0;

	for (int i = 0; i < num; i++)
	{
		for (int j = i; j < num; j++)
		{
			map[i][j] = s[idx++];
		}
	}

	solve(0);

}

문제의 접근방식과 아이디어를 그대로 소스코드로 구현하였습니다.

문제풀이 후기

DP나 DFS 등 다양한 알고리즘의 기본이 되는 백트래킹의 기초를 다지기 좋은 문제였습니다.

어렵지 않은 문제이지만, 꼭 백트래킹의 핵심만은 알고 넘어가면 좋을 것 같습니다!

문제의 조건 자체를 문자열에서 배열로 바꿔서 이해하기 쉽게 만드는 것 이 아이디어 였습니다.

감사합니다.