[Python]알고리즘 문제풀이4

백준 2775번: 부녀회장이 될테야 문제

 

문제

 

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

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

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

 

풀이

 

우선 처음에는 이 문제에 어떠한 규칙이 있을까 싶어서 3층 정도까지를 대략적으로 수를 나열해보았다.

하지만 규칙을 찾을 수 없었고, 결국은 주어진 0층 1호부터 k층 n호까지 거주하는 인원을 가상의 배열을 만든 다음, 가장 마지막 수 (k층 n호 거주인원)를 실제로 출력하는 방법밖에 없다고 생각했다. 

 

각 호실에서 사는 사람의 수를 표로 나타냈을 때는 아래와 같다.

4층	1	6	21	56	126
3층	1	5	15	35	70
2층	1	4	10	20	35
1층	1	3	6	10	15
0층	1	2	3	4	5

 

1. 우선 각 층의 1호에 사는 사람들은 모두 1명이므로, 분기를 구분해주었다.

if room==1:
        print(1)

 

2. 0층에서 n호까지 거주하는 사람들을 list화 했습니다. n호까지로 한 이유는 실제로 층수가 올라갈수록 해당 층의 거주 인원을 구할 때, n호 이후의 거주 인원은 고려하지 않아도 되기 때문이다. 

       apt = []
        f0 = []
        for r in range(1, room+1): #0층에서 n호까지 거주하는 사람들의 수를 list화
            f0.append(r)
       apt.append(f0)

-> appartment라는 list 내에서 각 인덱스가 층을 의미한다. 그리고 각 인덱스에 또 list가 요소로 들어가는데 이는 그 층의 각 호에 거주하는 거주 인원을 나타낸다. 즉 0층의 n호까지 사는 인원을 list 화 하면 아래와 같은 형태일 것이다. ( 층 = appartment의 index이다)

appartment = [ [1,2,3,4,...,n],[...]...]

 

3. 그리고 1층부터 각 층을 반복문으로 돌면서, n호의 거주 인원을 구하기 위해서, appartment list에서 (층-1) index에 해당하는 list에서 index 0~index n-1 까지의 합을 구하면 된다.

        for f in range(1, floor+1):
            f_people = []
            for r in range(room):
                num = sum(apt[f-1][:r+1])
                f_people.append(num)
             apt.append(f_people)

4. 그리고 가장 마지막 수를 출력한다.

print(apt[-1][-1])

 

최종코드

t = int(input())
 
for t in range(t):
    floor = int(input())
    room = int(input())
    if room==1:
        print(1)
    else: 
        apt = []
        f0 = []
        for r in range(1, room+1): 
            f0.append(r)
        apt.append(f0)
        for f in range(1, floor+1):
            f_people = []
            for r in range(room):
                num = sum(apt[f-1][:r+1])
                f_people.append(num)
            apt.append(f_people)
        print(apt[-1][-1])