[BeakJoon 17623] 괄호

안녕하세요. 이번 포스팅에서는 백준 17623 괄호 문제를 풀어보도록 하겠습니다.

 

문제는

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

17623번: 괄호

 

위 링크에서 확인하실 수 있습니다.

 

이 문제를 dynamic programming으로 접근해서 해결하였는데, dmap값을 기준으로 dp[n] -> val(x)=n인 x 중 최솟값으로 갱신하였습니다.

 

조금 더 풀어서 점화식으로 설명하자면,

 

dp[1] = "()"

dp[2] = "{}"

dp[3] = "[]"

 

dp[3]까지 위 초기값보다 더 작은 dmap을 갖는 괄호 문자열은 존재하지 않습니다. 따라서 3개를 위와 같이 초기화해 주었습니다.

 

...

 

dp[n]을 갱신할 때

 

i = 1 ~ n까지 dp배열을 순회하며, 만약에 dmap(dp[n-i] + dp[i]) < dmap(dp[n]) 이라면 

dp[n] = dp[n-i] + dp[i]으로 갱신해 주었습니다.

 

dp[n-i] + dp[i] 역시 각각 올바른 괄호 문자열이기 때문에 두 문자열을 합해도 올바른 괄호 문자열은 유지가 되고, 이전에 dp[n-i]와 dp[i]는 각각 dmap값을 기준으로 최솟값으로 저장되어 있는 상태이기 때문에 두 값을 합한 값과 현재 dp에 저장되어 있는 값만을 비교해 주었습니다.

 

이 문제는 추가로 괄호로 묶을 수 있는데, ( xxxxx... ) 이렇게 소괄호로 묶이면 xxxx... 값의 *2,

중괄호면 *3, 대괄호면 *5이기 때문에

 

현재 비교하는 값 n이 각각 2로 나누어지거나, 3으로 나누어지거나, 5로 나누어지는 경우

"(" + dp[i/2] + ")", "{" + dp[i/3] + "}", "[" + dp[i/5] + "]"의 값 역시 비교해 주었습니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

int t, n;
string dp[1004];
map<char, char> _map;
bool canReplace(string cur, string _repl) {
	if(cur == "") return true;
	if(cur.size() < _repl.size()) return false;
	if(cur.size() > _repl.size()) return true;
	
	string curNum = "", _replNum = "";
	for(int i = 0; i < cur.size(); i++) {
		curNum += _map[cur[i]];
		_replNum += _map[_repl[i]];
	}
	
	return (curNum > _replNum);
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	_map.insert({'(', '1'});
	_map.insert({')', '2'});
	_map.insert({'{', '3'});
	_map.insert({'}', '4'});
	_map.insert({'[', '5'});
	_map.insert({']', '6'});
	
	dp[0] = "";
	dp[1] = "()";
	dp[2] = "{}";
	dp[3] = "[]";
	
	for(int i = 4; i <= 1002; i++) {
		if(i%2 == 0 && canReplace(dp[i], "(" + dp[i/2] + ")")) dp[i] = "(" + dp[i/2] + ")";
		if(i%3 == 0 && canReplace(dp[i], "{" + dp[i/3] + "}")) dp[i] = "{" + dp[i/3] + "}";
		if(i%5 == 0 && canReplace(dp[i], "[" + dp[i/5] + "]")) dp[i] = "[" + dp[i/5] + "]";
		
		for(int j = 1; j <= i; j++) {
			if(canReplace(dp[i], dp[i-j]+dp[j])) {
				dp[i] = dp[i-j]+dp[j];
			}
		}
	} 
	cin >> t;
	while(t--) {
		cin >> n;
		cout << dp[n] << "\n";
	}
	
	return 0;
}

  

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.