[Coding test][브론즈II]BOJ #2775 부녀회장이 될테야(수학)

내 풀이

def apart(a,b): #a층b호
    if a == 0:
        return b
    if b == 1:
        return 1

        
    if lst[a][b-1] == -1: #만약 a층 b호가 계산이 안되어있다면,
        lst[a][b-1] = apart(a,b-1) + apart(a-1,b)
        
    return lst[a][b-1]

lst = [[-1 for i in range(15)]for j in range(15)] 
# n,k가 14층,14호까지 있으므로, 초기값을 14*14 2차원 배열로 나타낸다.
# 리스트를 for문 바깥에 두면, 초기화되지 않고 계산값을 유지한다.

import sys

t = int(sys.stdin.readline().rstrip())


for i in range(t):
    # lst = [[-1 for i in range(15)]for j in range(15)]
    k = int(sys.stdin.readline().rstrip()) #n,k는 1이상 14이하이다. 따라서 최대 14층, 14호까지 있다.
    n = int(sys.stdin.readline().rstrip()) 

    print(apart(k,n))

문제 정의

💡 문제분석

메모이제이션을 사용하지 않으면 시간초과가 걸려 애먹는 문제이다.
메모이제이션에 관한 블로그 글을 참고하고 풀어보자.
메모이제이션이란?

각 층을 나열해보면

여기서 규칙을 알 수 있는데,

a층 b호에 사는 사람의 수는 a-1층 b호 + a층 b-1호에 사는 사람 수를 합한 것과 같다.

apart(a,b) = apart(a,b-1) + apart(a-1,b)

일반적인 재귀함수로 호출해내면 시간복잡도는 O(2^n)이지만,
메모이제이션을 이용하면 시간복잡도는 O(n)이므로 메모이제이션을 이용해야한다.

💡 주의점

1. 메모이제이션(캐시)해야하므로 외부 테이블 작성(14*14)

2. 0층 n호는 모두 n을 리턴

3. k층 1호는 모두 1을 리턴

4. n층 k호에 사는 사람 수는 리스트로 접근하면
   lst[n][k-1]이다. (호가 1부터 시작함에 유의)