[BOJ 17428] K번째 괄호 문자열

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

17428번: K번째 괄호 문자열

 

- 문제 요약

 

길이가 N인 괄호 문자열 중에 사전 순으로 K번째인 문자열을 출력하시오.

K번째 괄호 문자열이 없는 경우에는 -1을 출력한다.

여기서 S가 괄호 문자열이면 (S)도 괄호 문자열이고, S와 T가 괄호 문자열이면 ST는 괄호 문자열이다.

또한 빈 문자열은 괄호 문자열이다.

(2<=N<=50, N은 짝수)

(0<=K<=2^N-1)

 

 

- 알고리즘 정리

 

우선 이걸 스택에 하나하나 push, pop 하면서 구하기에는 시간 복잡도가 터질 것 같으니 DP로 풀도록 하겠습니다.

DP 식의 정의를 어떻게 하냐가 문제인데.... 우선 스택 구조를 떠올리면서 DP 정의를 만들어보겠습니다.

 

dp[i][j] : 길이 n인 문자열을 만들 때 현재 ')' 보다 '('가 j개 많은 상황에서 앞으로 추가해야 할 문자열의 길이가 i일 때, 만들 수 있는 괄호 문자열의 개수

 

이렇게 정의했을 때, dp[i][0]는 '('이랑 ')'의 개수가 같다는 뜻이고, 그러면 dp[i][0]의 값은 길이 n인 괄호 문자열의 전체 개수가 됩니다.

 

대충 정의는 이렇게 짜 놓으면 될 것 같습니다.

문제는 점화식을 어떻게 구하냐인데, 이는 시뮬레이션을 하며 만들어보겠습니다.

 

- dp[0][0] -> 길이 n인 문자열을 만들 때 현재 두 괄호 문자의 개수가 같고, 앞으로 추가해야 할 문자열이 없을 때 -> 1

- dp 배열은 우선 0으로 세팅

- 현재 문자열에서 '('를 추가하면 dp 배열의 인덱스는 dp[i-1][j+1]

- 현재 문자열에서 ')'를 추가하면 dp 배열의 인덱스는 dp[i-1][j-1]

- '('가 ')'보다 사전적으로 앞섬

- dp[i-1][j+1]이 dp[i-1][j-1]보다 사전적으로 앞섬

- 단순 반복문보단 재귀 함수...?

 

위에 있는 메모들은 점화식을 만들어가며 의식의 흐름대로 적어놓은 것들입니다.

조금씩 생각이 정리가 되어가고 있으니, 이제 코드를 짤 준비를 해보겠습니다.

 

우선 반복문으로 dp[i-1][j-1], dp[i-1][j+1]을 활용해서 dp 배열을 채워줍니다.

그리고 재귀를 돌리면서 K번째 괄호 문자열이 없는 경우에는 -1을 리턴 받아서 예외조건을 걸러줍니다.

K번째 괄호 문자열이 존재하는 경우에는 채워놓은 dp 배열을 이용해서 괄호 문자열을 만들어주고 출력해주면 됩니다.

 

 

- 코드 작성

 

우선 dp 배열을 반복문으로 채우고, 예외조건을 거르는 재귀 함수와 괄호 문자열을 만들어주는 재귀 함수를 작성합니다.

문제에서 K의 제한을 2^N으로 두었으니, 최대 값은 2^50-1이 될 것입니다.

그냥 변수들과 dp 배열은 마음 편히 long long 타입으로 선언하겠습니다.

 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long ll;
ll n,k,dp[52][52];

ll f(ll i,ll j,ll k){
	if(i==1){
		return 1;
	}
	if(k>=dp[i][j]){
		return -1;	
	}
	if(k<dp[i-1][j+1]){
		return f(i-1,j+1,k);
	}
	return ((ll)1<<(i-1))+f(i-1,j-1,k-dp[i-1][j+1]);
}

void ff(ll n,ll a){
	for(int i=n-1;i>=0;i--){
		if(((ll)1<<i)&a){
			cout<<')';
		}
		else{
			cout<<'(';
		}
	}
}

int main(){
	cin>>n>>k;
	dp[0][0]=1;
	for(int i=1;i<=50;i++){
		for(int j=0;j<=i;j++){
			if(j==0){
				dp[i][j]=dp[i-1][j+1];
			}
			else{
				dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
			}
		}
	}
	ll a=f(n,0,k);
	if(a==-1){
		cout<<-1;
	}
	else{
		ff(n,a);
	}
	return 0;
}

코드 제출 결과

+를 -로 써서 30분 날리고.....

1 앞에 (ll) 안 붙여서 또 15분 날리고.....

멘탈도 날리고.......

그냥 플래티넘 이상 문제는 여유롭게 푸는 게 정신건강에 이로울 것 같습니다....