[파이썬] 백준 2775번

https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

 

문제

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

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

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

입력

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

출력

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

제한

• 1 ≤ k, n ≤ 14

 

 

---

전체 코드입니다.

 

T = int(input())

for _ in range(T):
    k = int(input()) # 층
    n = int(input()) # 호

    f0 = [x for x in range(1, n + 1)] # 0층 리스트

    for i in range(k): # 층 수 만큼 반복
        for j in range(1, n): # 1부터 n-1까지
            f0[j] += f0[j-1] # 층별 각 호실의 사람 수 변경
    print(f0[-1]) # 가장 마지막 수 출력

 

 

 

이 문제는 얼마전에 풀었던 ACM 호텔 문제와 비슷하다고 느꼈지만 그 문제는 수식으로 풀어야되는 것과 달리 이 문제는 리스트를 만들어 그 리스트의 인덱스를 출력해야하는 문제였습니다. 

 

 

 

일단 Test Case인 수 T를 입력 받습니다. 그리고 그 T만큼 층 k와 호 n을 입력 받은 후 층과 호에 맞게 리스트를 출력합니다.

 

f0 = [x for x in range(1, n + 1)] # 0층 리스트

 

이 코드를 작성하게 되면 0층의 리스트를 호 수에 맞게 출력을 해줍니다.

 

 

결과는 다음과 같습니다.

 

 

 

그 다음 층도 만들어야하니 층 수 만큼 반복을 해줍니다.

 

for i in range(k): # 층 수 만큼 반복

 

 

이와 같은 반복문을 통해 f0 리스트를 만들어줍니다.

 

 

 

하지만 여기서 거주 조건이 주어집니다. , “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다라는 것입니다. 따라서 층 별 각 호실의 사람 수를 변경하는 코드를 작성해주어야합니다.

 

for j in range(1, n): # 1부터 n-1까지
    f0[j] += f0[j-1] # 층별 각 호실의 사람 수 변경

 

방금 작성한 층 수 만큼 반복문 안에 이 코드를 작성해줍니다. 

 

 

 

 

실제 아파트는 위로 올라갈수록 층 수가 높아지지만 코드를 작성할 때는 인덱스 출력을 함에 따라서 아래로 갈수록 층 수가 높아지도록 구현하였습니다. 이 리스트에 적혀있는 수는 층 별 각 호실의 계약 조항에 따른 사람 수입니다. 1번째 줄은 1층, 2번째 줄은 2층입니다.

 

 

 

 

 print(f0[-1]) # 가장 마지막 수 출력

 

마지막으로 이 리스트의 가장 마지막 수를 출력하게 되면 해당 집의 거주민 수를 출력하게 됩니다.