백준 21.12.06. 2775번 - 부녀회장이 될테야

import sys

t = int(input())

for _ in range(t):
    k = int(input())
    n = int(input())
    people = [x for x in range(1,n+1)]

    for i in range(k):
        for j in range(1, n):
            people[j] += people[j-1]
    print(people[-1])

 

2층	1	4	10	20
1층	1	3	6	10
0층	1	2	3	4

• 우선 인구수는 위 표와 같이 진행됩니다.
• 여기서 봐야할 부분은 "k층의 n호의 인구수 = (k층의 n-1호의 인구수 + k-1층의 n호의 인구수)" 라는 점과
• "k층의 n-1호의 인구수 = (k-1층의 1호부터 n-1호까지의 인구를 합한 값)"과 같다는 점입니다.

 

• 우선 0층의 인구상황을 리스트로 만들어둡니다.
• 그리고 중첩 반복문을 사용하여 i층의 j호의 인구를 구해가면 됩니다.
• people리스트는 초기에는 0층의 인구를 나타냈지만 중첩반복문을 실행하며 i층의 인구를 나타내기 시작합니다.
• 중첩반복문에서 people[j]는 i-1층의 j호의 인구를 뜻하며, people[j-1]는 i층의 j-1호의 인구를 뜻합니다.
  • 연산하기 전 : 202호의 인구를 구할 때, i가 1(2층)이고 j가 2(2호)라면 people = [1,3,6]입니다.
  • 하지만 people[j](연산을 마친 2층의 j호 값) = people[j](연산을 하지 않은 1층의 j호값) + people[j-1](이미 연산을 마친 2층의 j-1호 값)이 되므로 연산을 마치면 people = [1,4,6]이 됩니다.
• 따라서 해당 연산을 마치면 people[j]는 i층의 j호의 인구를 뜻하게 됩니다.
• 이처럼 모든 연산이 끝나고 나면 갱신된 리스트의 마지막 값을 출력해주면 됩니다.