[Algorithm] 백준 - 파스칼 삼각형 (15489번)

문제

[백준] 파스칼 삼각형

사용 알고리즘

- 동적계획법 (Dynamic Programming)

해결방법

• 파스칼의 삼각형은, x == 0 일땐 무조건 1을 가진다
• dp[y][x] = dp[y-1][x-1] + dp[y-1][x] 
• 대칭구조 이므로, 절반만 dp를 채우고, 내부 합을 구할 때 dp 값이 없는 경우, 대칭위치의 값을 사용해 연산한다
  • dp[3][0], dp[3][1]
  • dp[4][0], dp[4][1]
  • dp[5][0], dp[5][1], dp[5][2]
  • dp[6][0], dp[6][1], dp[6][2]
    ....

파스칼의 삼각형

소스코드

사용언어 : c++

#include <iostream>

using namespace std;

int dp[31][31];

int main()
{
    int R, C, W;

    cin >> R >> C >> W;

    for (int i = 1; i < 31; i++) {
        dp[i][0] = 1;
    }

    for (int i = 3; i < 31; i++) {
        for (int j = 1; j <= i / 2; j++) {
            if (j == i/2 && i%2 == 0) continue;
            dp[i][j] = (dp[i-1][j] ?: dp[i-1][j-1]) + dp[i-1][j-1];
        }
    }

    int res = 0;
    for (int i = 1; i <= W; i++) {
        for (int j = 0; j < i; j++) {
            int num = dp[R+i-1][C+j-1] ?: dp[R+i-1][(R+i-1) - (C+j-1) - 1];
            res += num;
        }
    }

    cout << res;

    return 0;
}

x ?: y

* c++17 부터 간단한 대안 연산자가 도입되어 3항 연산자를 더 간단히 사용할 수 있다

 

 

한줄평

메모리 초과를 우려해 dp를 반만 채웠는데, 굳이 그렇게 안해도 됐었다. ㅎㅎ