Baekjoon 2775번 부녀회장이 될테야

Baekjoon 2775번 부녀회장이 될테야

https://www.acmicpc.net/problem/2775

3층	1호 1명	2호 1+{1+(1+2)}명	3호 1+{1+(1+2)}+{1+(1+2)+(1+2+3)}명
2층	1호 1명	2호 1+(1+2)명	3호 1+(1+2)+(1+2+3)명
1층	1호 1명	2호 1+2명	3호 1+2+3명
0층	1호 1명	2호 2명	3호 3명

다음과 같은 규칙이 존재할 때 숫자를 세는 것을 List를 이용하는 것이 편하다고 생각했지만
List를 2번 돌린다고 생각하니 시간복잡도가 너무 복잡해져서 결과의 만족도에 실망감이 크다. 최소 시간복잡도를 n^2로만이라도 잡는다면 좋겠는데.... 나의 한계를 맞보다...

# 첫 제출본 - 성공 그러나 시간복잡도 n^3

T=int(input())
for t in range(T):
    k=int(input()) #층 floor
    n=int(input()) #room Num
    LowfloorList=[x+1 for x in range(n)]
    UpperfloorList=[]
    sumLow=0
    
    for i in range(k):
        for j in range(n):
            sumLow += LowfloorList[j]
            UpperfloorList.append(sumLow)
        sumLow=0
        LowfloorList = UpperfloorList
        UpperfloorList =[]
    
    print(LowfloorList.pop())

ALL RIGHT RESERVED TWINSTARINFO