[코드업 3701] 파스칼의 삼각형

조합을 구하는 동적계획법 알고리즘을 조합을 구하는 동적계획법 알고리즘을 사용하면 간단하게 풀 수 있는 문제였다. 조합의 n값이 40 이상만 되도 int 자료형으로 표현할 수 없는데 이런 경우를 방지하기 위해 unsigned long으로 캐스팅해주면 문제는 없다.

 

#include <cstdio>

using namespace std;

unsigned long combCache[100][100];

unsigned long comb(int n, int r) {
    if (n == r || r == 0 || n == 0) {
        return 1;
    }
    else {
        if (combCache[n][r]) {
            return combCache[n][r];
        }
        else {
            return combCache[n][r] = comb(n - 1, r - 1) + comb(n - 1, r);
        }
    }
}

void pascal(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            printf("%lu ", comb(i, j));
        }
        printf("\n");
    }
}

int main() {

    int n;
    scanf("%d", &n);

    pascal(n);

    return 0;
}

 

참고로 앞으로 C++를 쓰더라도 cout, cin은 알고리즘 문제에서 사용하면 지양해야 한다. input, output 성능으로 실패하지 않도록 하자 ㅠ.ㅠ