[백준 2775번] 부녀회장이 될테야 파이썬풀이 DP

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

2775번: 부녀회장이 될테야

 

DP문제에 익숙하지 않은채 푼 문제였다

브1~실버 수준의 DP문제를 풀며 느낀건 비슷비슷한 문제들같다는 느낌이다

 

주어진 초기정보들로 문제에서 요구하는 조건을 만족하는 상황(dp[i]) 를 점화식형태(a.n+1 = a.n + f(x) ) 만들어 for문의 범위를 조정해 풀어가는느낌

 

2775번문제같은경우 파이썬에서 제공하는 인덱스 슬라이싱기능을 이용하여 풀었다.

n층 1호는 전부 1명이 사는게됨으로 

문제에서 4층 4호를 구해라할때 초기 배열을 [[1~4],[1],[1],[1],[1]]로 초기화한후 (0층은 n호수까지)

2중 for문으로 주어진 조건을 만족하는 인원수를 채워나가도록했다. 

 

time=int(input())

for test_case in range(time):
    k=int(input())
    n=int(input())    
    dp=[[ i for i in range(1,n+1)]]
    [dp.append([1]) for i in range(k)]
    #print(dp) # 호수별 인원
    
    #0은 기본
    for i in range(0,k):
        for j in range(2,n+1):
            dp[i+1].append(sum(dp[i][:j]))
        
    print(dp[-1][-1])