2775) 부녀회장이 될테야

📌 문제 탐색하기

• k층 n호에 살고 있는 사람의 수 구하기
• a층 b호에 사는 사람은, a-1층의 1호부터 b호까지의 사람들의 수의 합

가능한 시간복잡도

K층의 N번째 사람 수를 구할 때 까지 총 O(K) * O(N)번의 연산이 필요.
K와 N 모두 최대 14이고, 최대 연산수는 196
시간제한 : 0.5

알고리즘 선택

DP : 앞에 계산해 놓은 값을 재활용해 뒤의 문제의 답을 구하는 방식

📌 풀이하기

1. a층 b호 사람은 (a층 b-1호의 사람) + (a-1층 b호의 사람)
2. 관계식 구하기
   dp[b] += dp[b-1]

📌 코드 설계하기

1. 문제의 input을 받는다.
2. 가장 작은 문제의 답, 0번째 층의 사람 수를 기록한다.
3. 설계한 관계식에 맞게 DP 탐색을 진행한다.

📌 시도 회차 수정 사항 (Optional)

📌 정답 코드

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    K = int(sys.stdin.readline()) # 층
    N = int(sys.stdin.readline()) # 호

    # 0번째 층의 사람수
    DP = [i for i in range(1, N+1)]

    for a in range(K):
        for b in range(1, N):
            DP[b] += DP[b-1]
            
    print(DP[N - 1])