한 변의 길이가 d인 정십이각형을 만들 수 있는 방법의 수를 세는 C++ 프로그램

숫자 d가 하나 주어져 있다고 가정해 보겠습니다. 한 변의 길이가 1인 정사각형 타일과 정삼각형 타일이 무한히 많이 있다고 할 때, 이 타일들을 조합하여 한 변의 길이가 d인 정십이각형(12각형)을 만들 수 있는 방법이 총 몇 가지인지 구하는 것이 이 문제의 목표입니다. 만약 답이 너무 커진다면 결과를 998244353으로 나눈 나머지를 반환하면 됩니다.

풀이 접근 방법

이 문제는 다음 단계에 따라 해결할 수 있습니다.

b := 2*d - 1
c := 1
i를 2부터 d-1까지 1씩 증가시키며 반복:
    b := b * (2*d - i)
    c := c * i
return (b / c)

이 알고리즘은 결국 이항계수 C(2d−1, d)를 계산하는 것과 같습니다. 반복문이 진행되는 동안 분자에는 (2d−1)부터 (d+1)까지의 값이 차례대로 곱해지고, 분모에는 2부터 (d−1)까지의 값이 누적됩니다. 따라서 최종 결과는 (2d−1)! / (d! × (d−1)!) 형태가 되어, 정십이각형을 구성할 수 있는 경우의 수를 정확히 세어 줍니다.

C++ 구현 예제

아래 구현을 통해 더 쉽게 이해할 수 있습니다.

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

int solve(int d){
    int b = ((d << 1) - 1);
    int c = 1;
    for (int i = 2; i < d; i++){
        b *= (d << 1) - i;
        c *= i;
    }
    return (b / c);
}
int main(){
    int d = 1;
    cout << solve(d) << endl;
}

입력

1

출력

1

d가 1일 때는 정십이각형을 만들 수 있는 방법이 한 가지뿐이므로 출력값이 1이 됩니다. 위 코드에서 비트 시프트 연산자 (d << 1)는 d에 2를 곱한 값과 동일하다는 점도 참고하면 좋습니다.