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

다이나믹 프로그래밍이라는 알고리즘을 사용하는 문제이다.

"다이나믹 프로그래밍"이란, 동적 프로그래밍이라고 하는데

어떤 목표까지를 도달하기 위해 이전의 결과 값들이 필요한 프로그램을 말한다.

 

뭐 어떻게 보면 그냥 처음부터 끝까지의 값들이 다 필요하니깐 다 저장해야한다는 것이다.

import sys
T=int(sys.stdin.readline())
for _ in range(T):
    k=int(sys.stdin.readline()) #k층
    n=int(sys.stdin.readline()) #n호
    l1=[i for i in range(1, n+1)]
    for j in range(k):
        l2=[]
        for i in range(1, n+1):
            l2.append(sum(l1[:i]))
        l1=l2
    print(l1[n-1])

그래서 일단 list를 두개를 만들었다.

하나는 이전 층의 n호까지의 거주민 수를 1호부터 차례대로 쓴 것이고(l1)

l2는 구해야하는 층의 n호까지의 거주민 수의 리스트를 만들었다. 

그리고 반복문을 통해서 현재 층의 거주민을 호별로 append 해주었다.

 

좀 더 좋은 방법이 있으면 언제든 댓글을 남겨주세요:)