Study/알고리즘

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

혤리 2020. 2. 7. 23:50

문제 링크 : https://www.acmicpc.net/problem/2775

 

2775번: 부녀회장이 될테야

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

www.acmicpc.net

from copy import deepcopy

for _ in range(int(input())):
    k = int(input()); n = int(input())
    base = [i for i in range(1,n+1)]
    for i in range(k):
        temp = deepcopy(base)
        for j in range(1,n+1):
            tmp = 0
            for s in range(j):
                tmp += temp[s] 
            base[j-1] = tmp
    print(base[n-1])

과연 deepcopy를 써야하는 것일지 문제를 다시 읽고 종이에 그려?봤더니

결국 (자신과 같은 층에서 전 호수의 사람 수)+(전 층에서 같은 호수의 사람 수)가 된다.

for _ in range(int(input())):
    k = int(input()); n = int(input())
    base = [i for i in range(1,n+1)] 
    for _ in range(k):
        for i in range(1,n):
            base[i] += base[i-1]
    print(base[n-1])

 

+ 아니 진작에 생각 좀 하고 풀면 되는 것을 왜 두번 일을 하게 만들까... 생각해!!