[백준] 2775번: 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

문제 이해

아래 층부터 채워나가면 된다. 

각 칸의 패턴을 파악하면 금방 식을 세워서 해결할 수 있다. 

	1호	2호	3호
1층	0+1 = 1	1+2 = 3	1+2+3 = (1+2) + 3  = 6
0층	1	2	3

보면 각 k층 n호는 k-1층의 1부터 n호까지의 합인데,

k-1층의 1부터 n-1호까지의 값이 k층 n-1호에 있으므로, k-1층 n호 + k층 n-1호의 값을 더하면 된다.

 

주어지는 테스트 케이스가 여러 개여서, 그냥 14층 14호까지 다 값을 저장했다가

바로 좌표로 찍어버릴까 하다가, 그냥 각 테스트 케이스별로 표를 채워 나갔다.

 

문제에 테스트 케이스(T)가 최대 몇 개인지 언급을 안해서, 테스트 케이스가 너무 많을 때는 사실 14층 14호까지 채우고 좌표찍는 게 빠를 것이다. 

작성 코드

#include <iostream>
#include <vector>

using namespace std;

int t; // 테스트 케이스 개수
int k, n; // 층, 호
int arr[14+2][14+2];
vector<int> ans;

int main(void){

    // 0층 채우기
    for(int j = 1; j<=14; j++){
        arr[0][j] = j;
    }

    // 입력 받기
    cin >> t;
    for(int i = 0; i<t; i++){
        cin >> k >> n;
        
        // 해당 층까지 올리기
        for(int i = 1; i<=k; i++){
            for(int j = 1; j<=n; j++){
                arr[i][j] = arr[i][j-1] + arr[i-1][j];
            }
        }
        ans.push_back(arr[k][n]);
    }

    for(int i = 0; i<ans.size(); i++){
        cout << ans[i] << "\n";
    }
    return 0;
}