[수학][BOJ / Python] 2775 - 부녀회장이 될테야

2775번: 부녀회장이 될테야

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

 

풀이

수학 문제다.

가장 아래층인 0층은 i호당 i호를 살고 있다.

1호 - 1명, 2호 - 2명...

그리고 a층의 b호에 살려면 자신의 아래층의 1호부터 b호까지 사람들의 수의 합만큼 사람이 살아야 한다.

0층 1 2   3   4   5   6 

1층 1 3   6   10  15  21 

2층 1 4   10  20  35  56 

수열의 점화식은 d[i][j] = d[i-1][j] + d[i][j-1] 이 된다.

 

위의 표를 잘 보면, 1층의 2호에 사는 6명을 구할 때 0층의 1, 2, 3명을 구할 필요 없이, 0층의 2호에 사는 사람과 1층의 2호에 사는 사람을 더하면 된다. 이후에도 동일한 규칙이 적용된다!!

 

코드

for _ in range(int(input())):
    k=int(input());n=int(input())
    ho=[i for i in range(1,n+1)] # 아파트 호수 1,2,3,4...호
    for i in range(k): # 층의 높이만큼 반복
        for j in range(1,n): # 각 층의 1호(Index 0)는 생각할 필요가 없으므로 생략한다. n-1호까지 계산.
            ho[j]+=ho[j-1] # 호수에 이전의 호의 값을 더한다. 
        print(ho[n-1]) # 인덱스로 계산해야 하니 n-1의 값을 출력