백준 1023: 괄호 문자열

https://www.acmicpc.net/problem/1023

 

서두

내가 풀 문제를 고를때는 다른 분들이 정리하신 문제집에 수록된 문제들을 살펴서 괜찮아 보이는 것을 잡아서 해결한다.

그런데 이 문제는 약간 다르다. 내가 풀지 않은 문제 중 가장 작은 번호(1023)를 가지고 있었기에 이 문제에 관심을 가졌다.

 

분명 내가 가장 자신있는 알고리즘은 다이나믹 프로그래밍이다. 점화식을 잘 세우면 해결할 수 있기 때문이다.

그런데, 이 문제는 태그가 다이나믹 프로그래밍을 가졌지만, 해결방안이 전혀 떠올려지지 않았다.

결국 이 문제의 해결은 요원한채 끝날 뻔했다.

 

다른 문제에서 실마리를 얻다

어느날 문제집을 뒤지던 중 문제 하나를 발견했다.

 

https://www.acmicpc.net/problem/2248

이 문제를 보자마자, 이 문제의 해결책이 위의 문제를 해결할 열쇠인 것은 금방 알아챘다.

이것도 해결책을 전혀 모르겠지만, 다른 문제도 풀 수 있을 것이라 기대해 평소와 달리 바로 구글링을 거쳤다.

 

2248 문제는 직접으로 DP를 사용하지 않는다. 이항 계수를 구할 때 DP를 통해 계산해서, 이것을 활용하였다.

만약 처음에 0을 선택했을 때, 뒤에서 있을 수 있는 모든 경우의 수를 전부 더했을 때, 이것이 현재의 사전 순보다 크거나 같다면, 0을 고르고 아니라면 1을 고른다. 1을 고른 경우엔, 사전 순을 모든 경우의 수 만큼 빼면 된다.

 

예를 들어서, N = 6, L = 3이라 가정해서 0을 골랐을 경우, N = 5, L = 3일 때, L개 이하의 비트를 고르는 경우의 수를 전부 더한다. 이를 위한 이항 계수로

 

(5개 중 0개를 고를 때 + 5개 중 1개를 고를 때 + 5개 중 2개를 고를 때 + 5개 중 3개를 고를 때)

 

를 전부 더한다. 그렇다면, 현재 위치에서 0을 골랐을 때, 최대의 경우의 수를 구할 수 있다.

만약 현재의 사전 순이, 최대의 경우의 수보다 작다면, 해당 위치에 0을 충분히 고를 수 있다는 의미이고, 아

니라면 0을 선택한 것보다 사전순이 더 뒤에 있다. 따라서 1을 골라야한다는 의미이다.

 

그렇게 나온 코드는 다음과 같다.

#include <iostream>

using namespace std;
using ll = long long;
int N, L;
ll I, dp[33][33];
string ans = "";


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> L >> I;
	dp[0][0] = 1;
	for (int i = 1; i < 33; i++)
	{
		dp[i][i] = 1;
		dp[i][0] = 1;
	}
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= i; j++)
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
	while (N > 0)
	{
		if (L == 0)
		{
			while (N-- > 0) ans.push_back('0');
			break;
		}
		ll s = 0;
		for (int i = 0; i <= L; i++)
			s += dp[N - 1][i];
		if (s >= I)
		{
			ans.push_back('0');
		}
		else
		{
			ans.push_back('1');
			--L;
			I -= s;
		}
		--N;
	}
	cout << ans << '\n';
}

다시 본 문제로

이제 다시 문제로 돌아오자, 이 문제는 바로 전에 해결한 문제처럼 비트 수로 해결하는 문제가 아니라, 괄호가 짝지어지 않는 문자열을 사전순으로 나열했을 때, K번째에 오는 문자열을 구하는 문제다.

 

위 문제에서 얻은 것을 활용한다면, '('을 골랐을 때, (뒤의 모든 경우의 수 - 짝이 이어지는 경우의 수)를 고르면 된다.

(뒤의 모든 경우의 수)는 각 문자열이 '(' 혹은 ')'을 고르는 모든 경우의 수이기에,  2^{n - 1}(n은 현재 길이) 로 바로 구할 수 있다. 그렇다면 (짝이 이어지는 경우의 수)는 어떻게 구할 수 있을까?

 

그렇다, 위의 문제에 이항계수를 DP를 통해 해결했듯 위 문제도 (짝이 이어지는 경우의 수)를 DP로 구할 수 있다.

 

DP[현재 남은 길이][짝지어지지 않은 괄호 수] = DP[현재 남은 길이 + 1][ 짝지어지지 않은 괄호 수 + 1] 

+ if( 짝지어지지 않은 괄호 수 > 0) DP[ 현재 남은 길이 + 1 ][ 짝지어지지 않은 괄호 수 - 1];

 

여기서 현재 남은 길이가 N과 동일할 때, 짝지어지지 않은 괄호 수가 0일 때 1이고 아니면 0이다.

이런 방식으로 짝이 이어지는 경우의 수를 구할 수 있다.

ll solve2(int n, int a)
{
	ll& ret = dp[n][a];
	if (n == 0)
	{
		if (a == 0) return ret = 1;
		return ret = 0;
	}
	if (ret >= 0) return ret;
	ret = 0;
	if (a > 0) ret += solve2(n - 1, a - 1);
	ret += solve2(n - 1, a + 1);
	return ret;
}

이제, 이것을 활용해서 정답을 구해보자.

void solve(int n, int a, ll r)
{
	if (n == 0) return;
	if (r == 0)
	{
		while (n--)
		{
			ans.push_back('(');
		}
		return;
	}
	ll s = pow(2, n - 1) - ((a + 1 > 0) ? dp[n - 1][a + 1] : 0);
	if (s > r)
	{
		ans.push_back('(');
		solve(n - 1, a + 1, r);
	}
	else
	{
		ans.push_back(')');
		solve(n - 1, a - 1, r - s);
	}
}

위에선 while문을 활용했지만, 이번엔 재귀를 사용해 반복을 하였다.

 

놀랍게도, 이 코드는 틀렸다. 분명 이론 상으로 맞을텐데 왜 틀렸는지 이해가 되지 않았다.

결국, 예제를 일일히 만들어서, 문제점을 찾으려 노력했다.

1 0에서 부터, 1 1, 1 2, 2 0, 2 1, 2 2, 2 3 ....

이런 식으로 예제를 만들며 반례를 찾았고, 겨우 하나 찾았다.

 

4 7

답: )(()

오답: )())

 

이렇게 된 원인은 )(()을 짝이 맞는 괄호로 계산되었기 때문이다.

따라서, 이전에 짝지어지지 않은 괄호가 한 번 음수가 되었다면, 그 뒤는 어떻게 짝지어져도, 그 괄호는 짝이 맞는 괄호가 될 수 없다는 것을 내가 괄시해버렸던거다.

그렇게, 재귀에 매개변수 하나(짝지어지지 않은 괄호가 음수가 된 적이 있는지 여부)를 추가해서 다시 코드를 구성했다.

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;
ll N, K, dp[53][53];
string ans = "";
ll solve2(ll n, ll a)
{
	ll& ret = dp[n][a];
	if (n == 0)
	{
		if (a == 0) return ret = 1;
		return ret = 0;
	}
	if (ret >= 0) return ret;
	ret = 0;
	if (a > 0) ret += solve2(n - 1, a - 1);
	ret += solve2(n - 1, a + 1);
	return ret;
}
void solve(ll n, ll a, ll r, bool f)
{
	if (n == 0) return;
	if (r == 0)
	{
		while (n--)
		{
			ans.push_back('(');
		}
		return;
	}
	if (a < 0) f = true;
	ll s = pow(2, n - 1) - ((!f) ? dp[n - 1][a + 1] : 0);
	if (s > r)
	{
		ans.push_back('(');
		solve(n - 1, a + 1, r, f);
	}
	else
	{
		ans.push_back(')');
		solve(n - 1, a - 1, r - s, f);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> K;
	memset(dp, -1, sizeof(dp));
	solve2(N, 0);
	solve(N, 0, K, false);
	if (pow(2, N) - dp[N][0] < K + 1) cout << -1 << '\n';
	else cout << ans << '\n';
}

문제를 많이 해결하는 것이 중요하다는 것을 느껴짐과 동시에, 스스로 해결해서 뿌듯한 문제였다.