<백준 문제풀이: 2775번> 파이썬 - 부녀회장이 될테야

1주일전에 풀려고 했다가 실패해서 다시 풀어본 문제이다:

시간 초과가 뜬 풀이

import sys

N = int(sys.stdin.readline())

zero_floor = [x for x in range(0, 15)]
def floor(k, n):
    if n == 1:
        return 1
    if k == 1:
        return zero_floor[n] + sum(zero_floor[:n])
    else:
        return floor(k-1, n)+floor(k, n-1) 

for i in range(N):
    k = int(sys.stdin.readline())
    n = int(sys.stdin.readline())
    floor(k,n)

저번에 풀었던 방식은 이렇게 각 k, n에 대하여 그에 알맞게 차근차근 각 호의 인원 수를 구하고 더해주고... 이를 반복해서 구하는 것이었다. 하지만 이렇게 하면 시간 초과가 떴었고, 이를 해결하기 위한 방법을 생각해내지 못했다.

제출한 정답

import sys

N = int(sys.stdin.readline())

apart_people = [[x for x in range(15)]]

for i in range(15):
    floor = []
    for j in range(15):
        floor.append(sum((apart_people[-1])[:j+1]))
    apart_people.append(floor)

for j in range(N):
    k = int(sys.stdin.readline())
    n = int(sys.stdin.readline())
    print(apart_people[k][n])

시간초과가 뜬 방식과 달리, 처음부터 모든 호수의 인원들을 찾아주고, 입력 받는 k, n값에 따라 바로 해당 호수의 인원을 출력하게끔 하면 된다. 이것이 시간이 더 오래 걸릴 줄 알았어서 애초에 시도를 안했었으나, 생각해보니 입력 받는 k, n 값마다 인원수를 계산하느 것이 더 비효율적이어서 시간이 더 오래 걸린 다는 것을 깨달았다.