문제출처 : https://www.acmicpc.net/problem/2775

문제 파악

“k층 n호에는 몇 명이 사는가?”를 출력하는 문제이다.

1. 0층 i호에는 i명이 산다.
   dp[0][i] = i

2. k층 n호는 아래층 1호부터 n호까지 사람 수의 합이다.
   dp[k][n] = dp[k][1] + dp[k][2] + ... + dp[k][n]

근데 dp[k][n-1]은
dp[k][n-1] = dp[k][1] + … + dp[k][n-1]이다.

즉,dp 점화식

dp[k][n] = dp[k][n-1] + dp[k-1][n]

오른쪽으로 한 칸(같은 층)

아래로 한 칸(아래층 같은 호)
이렇게 두 방향만 보면 되는 문제다.

해답 및 풀이

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    k = int(input())
    n = int(input())
    
    # dp[k][n] 생성 (0층~k층, 1호~n호)
    dp = [[0]*(n+1) for _ in range(k+1)]
    
    # 0층 채우기
    for i in range(1, n+1):
        dp[0][i] = i
    
    # 층과 호수 채우기
    for floor in range(1, k+1):
        for room in range(1, n+1):
            dp[floor][room] = dp[floor][room-1] + dp[floor-1][room]
    
    print(dp[k][n])