코드업(codeup) 3715 : 올바른 괄호 3 C언어

▶문제 : 올바른 괄호 3 (codeup.kr)

올바른 괄호 3

 

▶코드 작성

#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++해준다.