[BOJ 26740 // C++] Nawiasowania

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26740번 문제인 Nawiasowania이다.
문제는 아래 링크를 확인하자.

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

26740번: Nawiasowania

()가 k개 이어진 문자열의 올바른 부분괄호문자열의 개수는 k*(k+1)/2와 같음을 관찰하자.

 

또한 두 올바른 부분괄호문자열의 개수가 a1, a2인 두 괄호문자열 s1, s2에 대하여 s1 + ')' + s2 꼴의 문자열의 올바른 부분괄호문자열의 개수는 a1+a2가 됨을 관찰하자.

 

위 두 성질을 이용하면 N보다 작거나 같은 수 중 가장 큰 k(k+1)/2값을 찾아 ()를 그 개수만큼 출력하고 ')'를 출력한 뒤 N-k(k+1)/2에 대해 이 과정을 반복하는 것으로 문제를 해결할 수 있다.

 

각 N에 대하여 첫 단계에 작성하게 되는 ()가 이어진 문자열의 길이는 sqrt(N)에 비례함을 관찰하자. 즉, 이렇게 생성한 문자열의 길이가 10만을 넘지 않을 것임을 관찰하자. (자세한 증명은 단순계산이므로 생략한다.)

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N) {
		int cnt = 1;
		while (N >= cnt) cout << "()", N -= cnt++;
		cout << ')';
	}
}