백준-2775-부녀회장이 될테야

구현

• 해당 문제는 " a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다" 를 통해서 이전에 사용했던 값을 계속해서 활용해야 하는 문제이다.
• 즉 DP를 활용해서 풀 수 있다.

• 구현을 할 때 아래층의 1~b호까지의 합을 모두 구해야 하는데 , 이것은 동일한 층의 이전 호수에서 값이 구해져있다.
• 이를 활용하고, 자신 호수의 아래층 값만 더해주면 값을 구할 수 있다.

K = int(input())

for _ in range(K):
    k = int(input())
    n = int(input())

    # DP 테이블
    d = [[i for i in range(n+1)] for j in range(k+1)]

    for i in range(1, k+1):
        d[i][0] = 0
        d[i][1] = 1

        for j in range(1, n+1):
            d[i][j] = d[i-1][j] + d[i][j-1]

    print(d[k][n])

 

문제링크