[python/백준] 2775. 부녀회장이 될테야(B1)

📌 문제 탐색하기

👉 문제바로가기

T: Test case의 수
k, n: 층수, 호실(1 ≤ k, n ≤ 14)

처음에 우리가 알고있는 사람 수는 0층뿐입니다. k층 n호에 사는 사람의 수를 알기 위해서 0층부터 시작해서 각 층에 사는 사람의 수를 먼저 구한 후(작은 문제로 분해), k층까지 차례대로 올라가면서(큰 문제) 해답을 찾으면 됩니다.

📌 알고리즘 선택

다이나믹 프로그래밍으로 풀 수 있을지 어떻게 알 수 있을까요?
다음 조건을 만족하는 경우 우리는 다이나믹 프로그래밍을 사용할 수 있습니다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

a층의 특정 호실에 사는 사람의 인원수를 구하려면 (a-1)층에 사는 사람의 인원의 합을 구해야합니다. 0층으로부터 1층의 인원수를 구하고, 1층으로부터 2층의 인원수를 구할 수 있다는 점을 통해 해당 문제가 작은 문제로 나누어짐을 알 수 있습니다. 그리고 아래 층에서 구한 정답이 더 큰 문제의 정답을 구하는 데 사용되기 때문에 DP를 활용할 수 있겠네요.

시간복잡도

각 층별로 실행되는 시간복잡도는 아래와 같습니다.

• 1층(k=1): 1+2+...+n=n(n+1)/2 => O(n^2)
• 2층(k=2): 1+2+...+n=n(n+1)/2 => O(n^2)
• ...
• k층: 1+2+...+n=n(n+1)/2 => O(n^2)

각 층에 대한 시간복잡도는 O(n^2)인데 총 k층이므로 O(k*n^2)입니다. 테스트케이스마다 해당 코드를 수행하므로 최종적으로 시간복잡도는 O(T*k*n^2)가 됩니다.

📌 코드 설계하기

1. 테스트 케이스의 수(T)를 Input받고, 층수와 호실을 테스트 케이스 수 만큼 Input받습니다.
2. 0층의 초기 사람 수 리스트를 생성합니다.
3. 이전 층의 인원수 리스트를 이용하여 각 층에 대해 n호실까지 사람의 수를 계산합니다.
4. k층 n호실의 사람 수를 출력합니다.

📌 정답 코드

import sys

T = int(sys.stdin.readline())   #테스트 케이스 수
dp = []

for _ in range(T):
    k = int(sys.stdin.readline())   #층수
    n = int(sys.stdin.readline())   #호실

    k0 = [i for i in range(1, n+1)] #0층

    for _ in range(k):
        arr = []
        for j in range(n):
            arr.append(sum(k0[0:j+1]))  #아래 층수 n호까지의 합
        k0 = arr    #k0업데이트 (+1층의 인원수 배열이 됨)
    print(arr[n-1])   #k층 n호 사람의 수