티스토리 뷰

PS/Python

[PYTHON] 백준 알고리즘 #2775 부녀회장이 될테야

yoo.o 2020. 1. 16. 17:07
반응형

문제

 

2775번: 부녀회장이 될테야

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

www.acmicpc.net

 

풀이

야 주희야... 이런 아파트에서 살지마

 

처음엔 재귀로 짰다

파이참에서 돌리면 값은 다 나오지만 아무래도 재귀라서 시간초과가 뜬다

num = int(input())

def fun(a, b):
    if a == 0:
        return b
        
    else:
        s = 0
        for i in range(1, b+1):
            s += fun(a-1, i)
        return s

for i in range(num):
    k = int(input())
    n = int(input())
    print(fun(k, n))

 

 

 

이렇게 짜니까 맞았다

num = int(input())

for i in range(num):  # test case num

    k = int(input())
    n = int(input())

    arr = [[0 for col in range(n)] for row in range(k+1)]

    for a in range(1, n+1):  # 0층
        arr[0][a-1] = a

    for floor in range(1, k+1):
        for room in range(n):
            if room == 0:
                arr[floor][room] = 1
            else:
                arr[floor][room] = arr[floor][room-1] + arr[floor-1][room]

    print(arr[k][n-1])

2차원 배열을 어떻게 표현할지 고민했는데

생각해보니 원하는 크기만큼 0으로 다 채운 후 내용을 바꾸는게 제일 간단한것 같다

 

 

 

일반항을 찾아서 풀어도 된다

 

반응형