[백준] 2775. 부녀회장이 될테야

2775번: 부녀회장이 될테야

---

이 문제는 n과 k가 1부터 14 사이의 작은 수여서 O(n²)의 시간복잡도가 나오더라도 이중 반복문을 사용해 풀었다.

# 2775 부녀회장이 될테야

T = int(input())

for tc in range(1, T+1):
    k = int(input())
    n = int(input())

    house = [[0 for _ in range(n+1)] for z in range(k+1)]

    # 0층의 room들은 1, 2, 3 순으로 사람이 들어가 있다.
    for r in range(n+1):
        house[0][r] = r

    # k층 n호실에 사는 사람 수 = k-1층 1호실~n호실까지의 사람 수이므로
    # 이중 반복문을 이용한다.
    for floor in range(1, k+1):
        for room in range(1, n+1):
            house[floor][room] = sum(house[floor-1][0:room+1])

    print(house[k][n])

다른 언어로 풀이하신 분들 중에는 재귀로 푸신 분들도 많은데, 파이썬 언어 특성상 재귀를 사용하면 시간 초과가 나올 가능성이 높아서 파이썬 쓰시는 분들은 나처럼 이중 반복문을 쓰신 경우가 많은 것 같다.