[백준/C++] 16395번: 파스칼의 삼각형

문제&링크

https://www.acmicpc.net/problem/16395

 

풀이

1. 파스칼의 삼각형을 왼쪽으로 붙인다고 생각한다. 그 경우 직각이 왼쪽 하단에 위치한 하삼각 행렬이 된다.

2. 첫 번째 열의 모든 값과 열과 행이 같은 모든 값은 1이기에 초기화를 진행한다.

3. 2번에 위치하지 않은 값들은 해당 위치의 바로 위(map[i - 1][j])와 왼쪽 대각선 위(map[i - 1][j - 1])를 더해서 만든다.

4. 원하는 행 및 열을 찾아 출력한다.

 

코드

#include <iostream>

using namespace std;

int map[31][31];

int main() {
    for (int i = 1; i < 31; i++) {
        map[i][1] = 1;
        map[i][i] = 1;
    }
    
    for (int i = 3; i < 31; i++) {
        for (int j = 2; j < i; j++) {
            map[i][j] = map[i - 1][j] + map[i - 1][j - 1];
        }
    }
    
    int N, M;
    cin >> N >> M;
    cout << map[N][M];
    
}