[파이썬] 백준 2775번(브론즈1) : 부녀회장이 될테야

[문제]

문제 : 백준 2775번_부녀회장이 될테야

 

 

 

[코드]

import sys
input = sys.stdin.readline

T = int(input().strip())    # 테스트 케이스 수

for _ in range(T):
    k = int(input())    # 층 수
    n = int(input())    # 호 수

    # 아파트 2차원 배열 생성
    # [0] * (n+1) : 1행에 0 ~ n호까지 공간 확보
    # for _ in range(k+1) : 총 0층 ~ k층까지 행 확보 
    apt = [[0] * (n+1) for _ in range(k+1)]

    # 0층 초기화
    for i in range(1, n+1):
        apt[0][i] = i
    
    # 각 층 사람 수 계산
    for floor in range(1, k+1):
        for room in range(1, n+1):
            apt[floor][room] = apt[floor][room - 1] + apt[floor -1][room]
    
    # k층 n호 사람 수 출력
    print(apt[k][n])

 

 

 

[리팩터링 코드]

import sys
input = sys.stdin.readline

# 1. 미리 모든 경우를 계산해 놓기 위한 2차원 배열 만들기 (층 x 호)
dp = [[0] * 15 for _ in range(15)]  # 0층~14층, 1호~14호

# 2. 0층 초기화: i호엔 i명
for i in range(1, 15):
    dp[0][i] = i

# 3. 1층부터 14층까지 사람 수 채우기
for floor in range(1, 15):        # 1층부터 14층까지
    for room in range(1, 15):     # 1호부터 14호까지
        dp[floor][room] = dp[floor][room - 1] + dp[floor - 1][room]

# 4. 입력 받은 테스트 케이스 처리
T = int(input())
for _ in range(T):
    k = int(input())
    n = int(input())
    print(dp[k][n])

문제 조건에서 1 ≤ n ≤ 14, 0 ≤ k ≤ 14로 주어지니까 0~14까지 총 15칸 필요함

그래서 총 15×15짜리 표를 미리 만들었다.  (0층부터 14층, 1호부터 14호까지)

 

0층의 규칙 : i호엔 i명이 산다.

위층 계산은 점화식을 적용한다. 

k층 n호의 사람 수 = k층 (n-1호) + (k-1층 n호)

이 규칙을 코드로 옮기면 점화식을 이용한 DP(동적 계획법)이 된다.

 

 

 

[두 코드 차이점]

조건에 따라 사용할 코드가 다르다.

편의상 처음 작성한 코드를 A코드, 리팩토링 코드를 B코드라 하겠다.

• 테스트 케이스가 많다.
  • B 코드 (사전 계산)
• k, n 값이 커질 가능성 있다.
  • B 코드 (미리 다 만들어놓기)
• 테스트 케이스 1~2개뿐이다.
  • A 코드 (입력마다 새로 계산)
• 공간 최적화가 필요하다.
  • A 코드 (필요한 만큼만 배열 생성)
• 코드 구조를 직관적으로 보여주고 싶다.
  • A 코드

 

 

 

[제출 결과]