[백준 2775] 부녀회장이 될테야 / 파이썬

시간제한 : 1초

메모리제한 : 128MB

 

문제 :

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

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

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

 

입력 :

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다

 

출력 :

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

---

풀이

k층 n호에 살고 있는 거주민 수를 알기 위해서는 0층부터 k층까지 순차대로 구해야 한다.

 

각 층마다 거주하는 거주하는 수를 정리해보면 

0층 거주민은 그 거주민이 거주하는 호수 i와 같다. 

       ex) 0층1호 1명, 0층2호 2명 .... 0층n호 n명

1층 거주민은 0층의 1호부터 자신이 살고 있는 호수 i까지의 거주민 수의 합과 같다.

       ex) 1층1호 1명, 1층2호 3명, 1층3호 6명 ... 1층n호 n(n+1)/2명

 

따라서 k층 n호의 거주민은 k-1층의 1~n호까지의 거주민을 합친 것과 같으며,

이를 구하기 위해 반복문을 통해 0층부터 각 호에 해당하는 거주민 수의 리스트를 만들어 다음 층의 거주민 수에 반영하면 된다.

 

이를 아래 풀이에서는 아래 두 반복문을 통해 수행하였다.

1) 0부터 k층까지 반복하는 반복문

2) n호까지 반복하는 반복문

 

먼저, 2)의 반복문을 통해 각 층의 n호까지 거주하는 주민수를 구해 리스트에 넣어준다.

이때, 만약 k가 0이라면 (즉, 0층이라면) 거주민은 0부터 1씩 증가하여 리스트에 넣어주면 된다.

k가 0이 아닌 경우 base에 저장해 놓은 k-1층 거주민의 숫자를 합하여 리스트에 넣어준다.

 

반복문이 끝난 후 가장 마지막 주민수를 출력해주면 된다.

import sys
input = sys.stdin.readline

T = int(input())

adrs = []
for _ in range(T):
    k = int(input())
    n = int(input())
    adrs.append(tuple(k, n))
    
for k, n in adrs:
    resident = 0
    base = [i for i in range(1, n+1)]
    for j in range(k+1):    
        temp = []
        for x in range(n):
            if j == 0:
                resident = x+1
            else:
                resident = sum(base[:x+1])
            temp.append(resident)    
        base = temp

    print(resident)