[Python] 백준 풀기 2775 - 부녀회장이 될테야

파이썬 백준 2775번

브론즈 1

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

2775번: 부녀회장이 될테야

 

 

 

 

 

문제 보기

분류: 수학, 구현, 다이나믹 프로그램

 

 

 

 

 

문제 풀기

1층 1호를 시작으로 해당 위치의 집의 사람 수를 구한다. 해당 위치의 인원을 구하기 위해서는 그 이전 호수의 인원과 그 이전 층의 인원이 먼저 구해져 있어야 한다. 따라서, 1층 1호, 1층 2호, ... , 2층 1호, 2층 2호, ... , ?층 ?호 순서로 찾아 나간다.

 

 

작성 코드는

해당 층 호수의 +1 개 만큼 빈 리스트를 생성한다. 편의상 리스트 index 와 층, 호를 맞추기 위해서 하나를 더해줬다.

0층을 0, 1, 2, 3, ... 인원으로 초기화한다.

이중 for loop 을 돌리면서 각 층과 호수에 대해 인원수를 구한다. 그 집의 인원수는 이전 호수의 인원과 아래층의 인원의 합이다.

            apartment[floor][room] = apartment[floor][room - 1] + apartment[floor - 1][room]

해당 k, n 에 대한 집의 인원을 출력한다.

    print(apartment[k][n])

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline


def fnHowManyPeopleLive(k, n):
    apartment = [[0] * (n + 1) for _ in range(k + 1)]           ## 해당 층 호까지 빈 리스트 생성.
    for i in range(n + 1):          ## 0층을 0, 1, 2, 3, ... 으로 N + 1 개 만큼 초기화.
        apartment[0][i] = i
    
    for floor in range(1, k + 1):           ## 낮은 층, 호를 시작으로 각 집에 대해 인원 저장.
        for room in range(1, n + 1):
            apartment[floor][room] = apartment[floor][room - 1] + apartment[floor - 1][room]
    
    print(apartment)            # test print
    print(apartment[k][n])          ## 찾고자 하는 집의 인원 출력.


if __name__ == "__main__":
    T = int(inputdata().strip())
    for _ in range(T):
        k = int(inputdata().strip())
        n = int(inputdata().strip())
        
        fnHowManyPeopleLive(k, n)



# 2
# 1
# 3
# 2
# 3

# [
#     [0, 1, 2, 3], 
#     [0, 1, 3, 6]
# ]
# 6

# [
#     [0, 1, 2, 3], 
#     [0, 1, 3, 6], 
#     [0, 1, 4, 10]
# ]
# 10