백준 2884: 부녀회장이 될테야 (Python)

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

2775번: 부녀회장이 될테야

 

실패 흔적이 매우 많음,,

처음엔 당연히 재귀로 풀어야지라고 생각했다

재귀 어려워해서 재귀로 푸는 알고리즘 생각하는 것도 엄청 오래 걸림 ㅜㅜ

 

def res(k, n):
    result = 0

    for i in range(n):
        if k == 1:
            result += n * (n + 1) // 2
            break

        result += res(k-1,i+1)

    return result

t = int(input())

for i in range(t):
    k = int(input())
    n = int(input())
    result = 0

    for i in range(n):
        if k==1:
            result += n * (n + 1) // 2
            break

        result += res(k-1,i+1)

    print(result)

 

근데 시간 초과가 났다..!! 

그래서 다시 풀었는데

 

def res(k, n):
    if k == 0:
        return n

    result = 0

    for i in range(n):
        result += res(k-1,i+1)

    return result

t = int(input())

for i in range(t):
    k = int(input())
    n = int(input())
    result = res(k,n)

    print(result)

 

여전히 시간 초과 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그래서 재귀함수로 풀면 안 되는구나,, 깨닫고 다시 두뇌 풀가동

 

t = int(input())

for i in range(t):
    k = int(input())
    n = int(input())
    result = [i+1 for i in range(n)]

    for i in range(k-1):
        for j in range(1,n):
            result[j] += result[j-1]

    print(sum(result))

 

이렇게 간단했다니 ㅠㅠ

 

 

거의 낙서장...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

결국 저 빨간 네모가 문제 푸는데 쓴 알고리즘이다..ㅎ