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

📌 문제 탐색하기

목표

• 아파트에 해당 집에 거주민 수를 출력하기
• a층의 b호에 살려면 자신의 (a-1)층의 1호부터 b호까지 사람들의 수의 합 만큼 데려와 살아야한다.

입력값

• 첫 번째 줄에 테스트케이스 수 t가 주어진다. (t에 대한 제한은 주어지지 않는다.)
• 각 케이스마다 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 ≤ k, n ≤ 14)
  • ex)
  • 2 1 3 2 3

출력값

• 각 테스트케이스에 대해서 해당 집에 거주민 수를 출력한다.
  • ex)
  • 6 10

📌 코드 설계하기

해결 아이디어

• 시간 제한을 보면 0.5초이다. 약 5천만 번만 연산 가능하다는 뜻이다. 계속 재귀로 구현하면 시간복잡도가 굉장히 높을 것이므로 dp로 풀자.
• 어제 풀었던 피보나치 수열의 방법을 떠올리면 하나의 배열을 만들어서 한 번 계산을 진행하면 모두 배열에 저장을 해줬다.
• 그림을 그려서 생각해보면 자신의 왼쪽 집과 아랫층 집에 사는 사람의 수를 더한 값이 자신의 값이 된다.
• 따라서 다음과 같이 배열에 저장할 식을 세워보았다.

 

📌 정답 코드

import sys

arr = [[0] * 15 for _ in range(15)]

def find(k, n):
    if k == 0 or n == 0:
        return n
    if arr[k][n] > 0:
        return arr[k][n]
    arr[k][n] = find(k-1, n) + find(k, n-1)
    return arr[k][n]
t = int(sys.stdin.readline())

for i in range(t):
    k = int(sys.stdin.readline())
    n = int(sys.stdin.readline())
    print(find(k, n))

시간 복잡도 계산해보기

• 입력
  • 총 t번 입력을 받음 → O(k)
• find()
  • arr[n]이 있기 때문에 같은 n을 두 번 이상 계산하지 않음.
  • 점화식: find(k, n) = find(k-1, n) + find(k, n-1)
  • arr 때문에 각 위치가 최대 한 번만 계산된다.
  • 따라서 시간 복잡도는 O(k*N)이 된다.

최종 시간 복잡도: O(N)