[ 파이썬(python) ] 백준 2775 - 부녀회장이 될테야

📍 백준 2775 - 부녀회장이 될테야

백준 2775 - 부녀회장이 될테야

---

💡 나의 풀이

이 문제는 DP, 재귀로 풀 수 있지만, DP로 푸는방법이 시간이 훨씬 단축된다. 재귀로 풀때는 python3에서 시간초과에 걸리므로 pypy로 제출해야한다.

 

DP 풀이방법이다.

 

1. 0층의 i는 i명이 살기때문에 제일 아래는 [1, 2, 3, 4...]다.
2. 문제는 층수가 증가 할때마다 이전 층수의 1호부터 b호까지 더한값을 사용해야하는데 이때 DP가 쓰인다.
3. arr[i] += arr[i-1]로 1호부터 b호까지 값을 누적시킨다.
4. 층수가 올라갈때는 3번 반복문 바깥에 하나 더 선언한다. for _ in range(k)

 

재귀 풀이방법이다. a: 층, b: 호

1. 하단의 사진처럼 이전 index + 아래 index를 더해준다.
2. 종료 조건은 a == 0: return b, b == 1: return 1이다.

 

# DP
T = int(input())

for _ in range(T):
    k = int(input())
    n = int(input())
    floor = [i for i in range(1, n+1)]

    for _ in range(k):
        for i in range(1, n):
            floor[i] += floor[i-1]
    print(floor[-1])

# 재귀
def check(a, b):
    if not a:
        return b
    if b == 1:
        return 1
    return check(a, b-1) + check(a-1, b)

for _ in range(int(input())):
    k = int(input())
    n = int(input())
    print(check(k, n))