코드업(codeup)/C
코드업(codeup) 3715 : 올바른 괄호 3 C언어
starfish22
2022. 1. 17. 16:06
728x90
▶문제 : 올바른 괄호 3 (codeup.kr)
올바른 괄호 3
여닫는 괄호의 개수n 이 주어진다. (단, 1 <= n <= 15)
codeup.kr
▶코드 작성
#include <stdio.h>
int cnt;//올바르게 여닫는 경우의 수
int n;
void func(int i, int c)//(괄호 여닫는 횟수(열기+,닫기-) , 괄호 사용 횟수)
{
if (c < n * 2)//총 괄호의 수 = n*2 를 넘을 때까지
{
if (i + 1 <= n) func(i + 1, c + 1);//열 때 여닫은 횟수가 여는 괄호 개수 이하면 괄호 열기
if (i - 1 >= 0) func(i - 1, c + 1);//닫을 때 여닫은 횟수가 0이상이면 괄호 닫기
}
else if (i == 0) cnt++;//여닫은 횟수가 일치하면 cnt++
}
int main()
{
scanf("%d", &n);
func(1, 1);//괄호를 여는 것부터 시작
printf("%d", cnt);
return 0;
}
▶해석
재귀 함수로 모든 여닫는 경우의 수를 계산하였다. 함수 func의 인자는 i = 괄호를 여닫는 횟수 , c = 괄호를 사용한 횟수이다. 특히 i는 괄호를 열면 +1을 하고 괄호를 닫으면 -1을 한다.
i가 여는 괄호의 개수를 넘으면 더 이상 열 수 없으므로 if문으로 i+1 <=n을 해주었다.
i가 닫는 괄호를 너무 사용하면 음수가 되는데 그럼 올바른 괄호가 아니므로 if문으로 i-1>=0을 해주었다.
c값으로 모든 괄호가 사용된 것을 알면 i가 0일 때 올바르게 괄호가 성립되었으므로 cnt++해준다.
728x90