[백준] 부녀회장이 될테야

문제보기 - https://www.acmicpc.net/problem/2775

문제명    - 부녀회장이 될테야

난이도    - B1

문제유형 - DP

풀이일자 - 25.03.12

 

📌 문제 탐색하기

• k층 n호에 살려면 (k-1)층의 1호부터 n호까지 사람들의 합만큼 살아야 함
• 0층의 i호에는 i명이 삼
  • 1호에는 1명, 2호에는 2명, …, n호에는 n명
• 입력으로 k층 n호가 주어졌을 때 그 방에 사는 사람 수를 출력해야 함
  • 1 ≤ k, n ≤ 14

 

🛠 시간복잡도 확인

• k번 반복하면서 n개의 방을 순회하여 값을 갱신 -> O(k × n)

 

📌 코드 설계하기

1. 0층 초기화, 누적 계산하는 함수 만들기
   • 0층의 각 호실을 초기화
   • for 문을 사용하여 이전 값 누적 계산
   • residents[i] += residents[i-1] 활용
2. T, k, n 입력받기
   • int(input()) 활용
3. 입력받은 k, n 값을 함수에 적용하여 결과 출력하기
   • print(apartment_residents(k, n)) 호출

 

📌 정답 코드(1회차)

# 1. 0층 초기화, 누적 계산하는 함수 만들기
def apartment_residents(k, n):
    residents = list(range(1, n+1))
    
    for _ in range(k):
        for i in range(1, n):
            residents[i] += residents[i-1]
    
    return residents[-1]

# 2. T, k, n 입력받기
T = int(input())  
for _ in range(T):
    k = int(input())
    n = int(input())
    # 3. 입력받은 k, n 값을 함수에 적용하여 결과 출력하기
    print(apartment_residents(k, n))