[Python] 백준 BaekJoon 2775

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어

각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있다.

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

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때,

주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라.

단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

 

입력

첫 번째 줄에 Test case의 수 T가 주어진다.

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

 

출력

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

 

 

[풀이법]

우선 각 층마다 호수가 구분이 되어야 하는데, 추가적인 조건을 명확히 파악 후 코드를 작성해야한다

 

1. 층과 호수를 각각 따로 입력받아야 한다

 

2. 아래는 예제 첫 번째 테스트 케이스를 예시로 가지고 온 각 호수별 사람 수다

문제의 조건에 따르면, 몇 명씩 증가한다는 정확한 명시는 없지만 계산할 수 있는 방법은 아래와 같다

예를 들어 103호의 입주하고 싶다면, 한 층 아래의 1호부터 동일한 3호라인까지의 사람수를 봐야한다

1~3호 라인의 거주자 모두를 합한 수보다 적으면 입주할 수가 없다(최소 동일한 인원수 필요)

(실제로 이러면 절대 못살겠지만 .. ;;)

 

3. 2번의 조건을 만족하기 위해 가장 아래인 0층의 인구를 차례로 기록하기 위해 빈 배열을 생성한다

   이후 1씩 인원수를 1씩 증가시키며 입력받은 호수까지 배열을 생성한다

people = []
for peopleNum in range(1, num + 1):
    people.append(peopleNum)

 

4. 이후 각 층당 입력받은 호수까지 순차적으로 반복연산을 거쳐야한다

   이때 개념적으로 1층씩 올라갈 때마다 배열이 새로 생기는 것이 아닌, 0층의 배열을 재사용하게 된다

   즉, 이미 만들어진 [1, 2, 3, 4, 5 ··· ]의 배열을 가지고 연산을 진행하게 된다

   위 그림과 같이 102의 호수는 2이며, 2는 배열의 2번째 인덱스를 가리키게 된다

people[peopleNum] += people[peopleNum - 1] → 2 += 1

  [1, 2, 3, 4, 5 ··· ]의 2번째 인덱스의 -1번째 인덱스는 1이며, 둘을 더한 수는 3이다

  3이 바로 실제로 구하려는 102호의 인원수가 되는 것이다

  

  동일한 방법으로 103호를 구하기 위해서는 0층의 1, 2, 3호의 모든 인원수를 더해야 한다

 

  마지막으로 404호에 입주해야 한다면, 한 층 아래의 1호부터 4호라인까지 인원수만큼 필요하다

  1 + 5 + 15 + 35 = 404호에 입주하기 위해서는 56명의 인원이 거주할 수 있어야 한다

 

T = int(input())

for i in range(T):
    floor = int(input())
    num = int(input())
    
    people = []
    for peopleNum in range(1, num + 1):
        people.append(peopleNum)
        
    for floorNum in range(floor):
        for peopleNum in range(1, num):
            people[peopleNum] += people[peopleNum - 1]
            
    print(people[-1])