[백준 - Python] 2775. 부녀회장이 될테야 (DP)

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

 

코드

t = int(input())
dp = [[0 for _ in range(15)] for _ in range(15)]

# 0층 i호에는 i명 초기화
for i in range(1, 15):
    dp[0][i] = i
    
# 각 층 1호 값 초기화
for i in range(1, 15):
    dp[i][1] = dp[i-1][1]
    
for i in range(1, 15):
    for j in range(2, 15):
        dp[i][j] = dp[i][j-1] + dp[i-1][j]  # 같은 층 전 호수 dp값에 다른 층 같은 호수의 dp를 더해준다
        
for _ in range(t):
    k = int(input())
    n = int(input())
    print(dp[k][n])

 

어렵지 않은 DP 문제였다.

0층부터 있는 아파트고, 0층의 i호에는 i명이 산다고 문제에서 주어졌기 때문에

우선 0층의 각 호수를 저장해주었다.

 

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

는 계약 조항으로 인해

모든 층의 1호는 그 바로 아래층의 1호와 같은 사람 수만큼이 산다.

따라서, 각 층의 1호를 저장해 주었다.

 

층마다 올라가면서 각 층의 호수를 채워주었는데,

i층 j호에 사는 사람의 수는

i층의 j-1호에 사는 사람의 수에 i-1층 j호에 사는 사람의 수를 더해준 값과 같기 때문에

그 내용으로 점화식을 세워주었다.

 

마지막으로 k층 n호에는 몇 명이 사는지

저장된 dp테이블에서 인덱스로 값을 불러와 출력해주었다.