[백준 2775번-파이썬/Python] 부녀회장이 될거야

http://acmicpc.net/problem/2775

{코드}

for _ in range(int(input())):
	k, n = int(input()), int(input())
	residents = [i for i in range(1, n+1)]
	for _ in range(k):
		for j in range(1, n):
			residents[j] += residents[j-1]
	print(residents[-1])

{설명}

먼저 각 층의 1호에는 1명만 있고, 첫 번째 층(0층)에는 n호에 n명이 있습니다.

그리고 a층의 b호에 들어갈 거주민의 수는 a-1층의 b호까지의 거주민의 합과 같습니다.

즉, 0층의 거주민 리스트를 층의 갯수만큼 반복문을 돌리며 전 호의 거주민 수에 현재 저장되어 있는 거주민의 수를 더해주면 됩니다.

예시를 보며 더 설명하겠습니다.

층	1호	2호	3호	4호	5호
0	1	2	3	4	5
1	1	3	6	10	15
2	1	4	10	20	35

위의 표를 보면 1층의 1호에는 1명이 들어오고

2호부터는 0층의 1호+0층의 2호,

3호는 0층의 1호+0층의 2호+0층의 3호....와 같은 순서를 가지고 있음을 알 수 있습니다.

근데 3호를 구하기 위해 필요한 0층의 1호와 0층의 2호는 결국 1층의 2호의 값과 같으므로 1층의 2호에 현재 저장된 값인 0층의 3호를 더하면 되는 것입니다.