[백준 알고리즘] 2775번: 부녀회장이 될테야 (Python)

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

2775번: 부녀회장이 될테야

 

소스코드

 

 

풀이

동적 계획법 DP로 푸는 문제입니다.

 

먼저 0층에 거주하는 사람, i호에는 i명이 살고 있습니다. 즉, 0층에는 

1호: 1명, 2호: 2명, 3호: 3명 ...   이런 식으로 사람이 살고 있습니다. 

 

1층부터는 바로 아래층의 1호부터, 입력으로 주어지는 n호까지의 합의 사람이 해당 층 n호에 살고 있습니다.

 

3층, 4호에 사는 사람까지 나타내면 위와 같이 나타낼 수 있습니다. 

 

이러한 방식으로 코드로 구현하는데, 각 층의 해당 호수에 해당 호수 -1까지의 숫자를 계속해서 더해나가야 합니다. 

 

그렇기에

for i in range(k) : 층수

구문을 돌면서 각 층의 해당 호수에 거주하는 사람을 저장해두고,

 

for j in range(1,n): 호수

층수가 증가할 때마다 저장 되어 있는 값에 새로운 수를 추가해주시면 됩니다 !