코드업(codeup) 2652 : 극장 좌석 배치 2 C언어

▶문제 : 극장 좌석 배치 2 (codeup.kr)

극장 좌석 배치 2

 

▶코드 작성

#include <stdio.h>

int func(n, r)//nCr
{
    if (r == 1) return n;
    if (n == 0 || n == 1 || n == r) return 1;
    return func(n - 1, r - 1) + func(n - 1, r);
}

int main()
{
    int n, k, temp1, temp2;
    scanf("%d %d", &n, &k);

    temp1 = k + 1;//nHr 중 n
    temp2 = n - k - (temp1 - 2);//nHr 중 r
    if (temp2 < 0) {//r이 음수라면 경우의 수 : 0
        printf("0");
        return 1;
    }

    printf("%d", func(temp1 + temp2 - 1, temp2));//nHr = (n+r-1)Cr

    return 0;
}

 

▶해석

파스칼의 삼각형 점화식 nCr=(n-1)C(r-1)+(n-1)Cr 을 func함수로 구현하고, 중복 조합의 부정 방적식을 적용하여 풀이하였다.