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

# 1 3 6 10
# 1 2 3 4

def dynamic(data):
    floor = data[0]
    index = data[1]

    dp = [[0] * (index+1) for _ in range(floor+1)]
    
    for i in range(1,index+1):
        dp[0][i] = i
    
    for i in range(1,floor+1):
        for j in range(1, index+1):
            if j == 1:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[floor][index]

t = int(input())

data = [[0]*2 for _ in range(t)]

for i in range(t):
    for j in range(2):
        data[i][j] = int(input())

for i in data:
    print(dynamic(i))

이번 문제는 다음 조건에 맞게 각 테스트 케이스마다 주어진 k(층 수), n(호 수)에 몇 명이 사는지 구하는 문제이다.

 

“a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”

 

본인은 0층부터 1층까지의 값을 구하던 중, dp[i][j] = dp[i-1][j] + dp[i][j-1] 이라는 점화식을 도출할 수 있었고, DP 2차원 리스트를 활용하여 간단하게 풀이할 수 있던 DP문제였다 :)