[브론즈1]백준 2775번(부녀회장이 될테야) - 코테공부 36일차(2025.02.26)

 

문제유형

다이나믹 프로그래밍(동적 계획법)

풀이 방법 도출 과정

1. 아파트의 거주 인원을 계산하는 문제이다. 특정 층(k)와 호(n)에 몇 명이 살고 있는지 구해야한다.

2. 거주 규칙은 다음과 같다. 

3. 0층의 i호에는 i명이 거주한다.

4. k층의 n호에 살려면, 바로 아래층(k-1)의 1호부터 n호까지 거주하는 사람들의 합만큼 데려와야 한다.

 

5. 예를 등러 1틍과 2층의 3호까지를 살펴보자

1층

1호: 0호 1호(1명) -> 1명

2호: 0층 1호(1명) + 0층 2호(2명) -> 3명

3호: 0층 1호(1명) + 0층 2호(2명)  + 0층 3호(3명) -> 6명

따라서 1층 3호 (n호)거주 인원은 총 6명이다.

 

2층

1호: 1호 1호(1명) -> 1명

2호: 1층 1호(1명) + 1층 2호(3명) -> 4명

3호: 1층 1호(1명) + 1층 2호(3명)  + 1층 3호(6명) -> 10명

따라서 1층 3호 (n호)거주 인원은 총 6명이다.

 

6. 이를 재귀함수로 표현해보도록 하겠다

residence(k, n) = 1부터 n까지 더하기 residence(k-1, i)

즉, 동적 프로그래밍과 재귀함수를 활용하여 효율적으로 해결할 수 있다.

7. 이대로 계산을 해보도록 하겠다. 

시간 복잡도

시간 복잡도는  O(T*k*n)이다. 

코드 및 간단설명

동적 계획법을 사용하였다.

T = int(input())

def num_residents(k, n):
    # DP 테이블 초기화
    dp = [[0] * (n + 1) for _ in range(k + 1)]

    # 0층 초기화: i호에는 i명이 거주
    for i in range(1, n + 1):
        dp[0][i] = i

    # DP 점화식 적용
    for floor in range(1, k + 1):  # 1층부터 k층까지
        for room in range(1, n + 1):  # 1호부터 n호까지
            dp[floor][room] = dp[floor][room - 1] + dp[floor - 1][room]

    return dp[k][n]

for _ in range(T):
    k = int(input())
    n = int(input())
    print(num_residents(k, n))

다른 풀이

1)  조합 공식 사용

동적 프로그래밍을 사용하지 않고 푸는 방법도 존재한다. 이는 조합공식으로도 구현이 가능하다. 우리가 사용하는 n(n+1)/2를 일반화하면 나타나는 식은 comb(n+k, k+1)로 매우 편리하게 풀수도 있다. 

import math

T = int(input())
for _ in range(T):
    k = int(input())
    n = int(input())
    # 조합 공식: dp[k][n] = math.comb(n+k, k+1)
    print(math.comb(n+k, k+1))