[백준 / python] 2775번 부녀회장이 될테야

오늘은 DP(다이나믹 프로그래밍) 유형인 백준 2775번 문제, 부녀회장이 될테야를 풀어보겠습니다!

 

< 문제 확인 >

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

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

문제의 목표는 k층 n호에 몇 명이 살고 있는지를 출력하는 것입니다.

 

해당 아파트는 아주 신기한 규칙이 존재합니다.

바로 "k층 n호에는 (k-1) 층 1호부터 n호까지의 사람 수의 합이 거주하고 있는 것"입니다.

 

아래 그림을 통해 k층 n호에 몇 명이 살고 있는지 확인해 보겠습니다.

(단, 아파트는 0층부터 시작하고 왼쪽부터 오른쪽 방향으로 1, 2, 3, 4, ... 호)

예를 들어, 1층 2호에는 0층 1호 거주민 + 2호 거주민의 수를 계산한 3명이 살고 있습니다.

3층 3호에는 2층 1호 거주민 + 2호 거주민 + 3호 거주민의 수를 계산한 15명이 살고 있습니다.

 

위 그림을 그려보며 0층 1호부터 4층 4호까지 모든 거주민들의 수를 계산하던 중

중복되어 계산되는 부분을 찾아낼 수 있었습니다!

 

색으로 표현된 3층 3호의 15명을 구하기까지 2층 1호와 2호를 더하고 3호를 더하려는 순간!!

방금 계산한 숫자는 3층 2호를 구하는 수식이었던 것입니다!

 

즉, 단순하게 아파트 규칙에만 의존해서 k층 n호의 거주민 수를 구하지 않고

중복되어 계산되는 부분을 미리 저장하여 DP(다이나믹 프로그래밍) 알고리즘을 통해

필요한 계산값을 바로 가져올 수 있게 코드를 작성해야 할 것입니다!

따라서, 3층 3호의 거주민 수는 3층 2호 + 2층 3호로 빠르게 계산이 가능합니다!

 

📣 그림을 그려보면서 문제를 해결하니 너무 좋은 것 같습니다 ㅎㅎ

 

✔️ 가능한 시간복잡도

k와 n은 최대 14이므로, 전체 가능한 조합은 14 * 14 = 196입니다.

이는 작은 범위이므로 O(k * n) 정도의 시간복잡도로 충분히 해결할 수 있습니다!

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 테스트 케이스 수 T와 각 케이스의 k(층), n(호) 값을 입력 받습니다.

2. DP 테이블 초기화 및 0층의 모든 호수의 거주자 수를 미리 추가합니다.

3. 각 층과 호수에 대해, 아래층의 호수들의 합을 계산하여 현재 층의 호수에 저장합니다.

(단, dp[k][n] = dp[k][n-1] + dp[k-1][n]를 통해 효율적으로 계산합니다!)

4. 테스트 케이스에 대해 입력받고 저장된 DP 테이블에서 계산된 거주민 수를 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

무문 별하게 “맞았습니다”가 나올 때까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

---

📌 정답 코드

# DP 테이블 준비
dp = [[0] * 15 for _ in range(15)]

# 0층 거주민 수 초기화
for i in range(1, 15):
    dp[0][i] = i

# DP 테이블 채우기
for k in range(1, 15):
    for n in range(1, 15):
        dp[k][n] = dp[k][n-1] + dp[k-1][n]

# 테스트 케이스 입력
T = int(input())

for _ in range(T):
    k = int(input())
    n = int(input())
    print(dp[k][n])

다이나믹 프로그래밍 알고리즘을 통해 재미있는 문제를 풀어보았습니다!

직접 그림을 그리며 중복으로 계산된다는 점을 파악했을 때 기분이 좋았습니다 ㅎㅎ

DP 문제 유형들도 점점 적응하는 거 같아서 뿌듯합니다!

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no