(파이썬) 백준 2665. 부녀회장이 될테야

문제

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

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

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

입력

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

출력

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

구상

몇 호실인지 정하는 n을 입력받은 후 크기가 n인 리스트를 만든다. 각 요소는 1~n까지 초기화 한다.

for i in range(n):
        arr.append(i+1)

예를 들어 k = 2, n = 3이라면

이렇게 초기화한다. 우선 0층을 구성하는 것이다.

 

다음 1층으로 넘어가면 계약 조항을 지키도록 각 요소에 저장된 수를 변경한다.

 

p는 0부터 k까지 변하며 층을 나타낸다.

i는 p층 각 호를, j는 p - 1층 각 호를 나타낸다.

for p in range(k):
        for i in range(n-1, 0, -1):
            for j in range(i):
                arr[i] += arr[j]

i를 처음부터 증가시키면 이미 변한 값이 다음 호에 적용된다.

i를 증가시키는 경우 1층

1층 1호엔 1(0층 1호) + 2(0층 2호) 명이 살고, 1층 2호엔 1(0층 1호) + 3(1층 1호) + 3(0층 2호) 명이 살게 된다.

그래서 변한 값이 반영되지 않도록 끝에서부터 시작한다.

i를 감소시키는 경우 1층

i를 감소시키는 경우 2층

print(arr[n-1])

n호실에 사는 사람 수를 출력한다.

코드

test = int(input())

for t in range(test):
    arr = list()
    k = int(input())
    n = int(input())
    for i in range(n):
        arr.append(i+1)
    for p in range(k):
        for i in range(n-1, 0, -1):
            for j in range(i):
                arr[i] += arr[j]
    print(arr[n-1])

4중 for문을 사용해서 시간 초과가 나지 않을까 했는데, k와 n이 14까지로 제한되어 있어 그러진 않았다.