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

2775번 부녀회장이 될테야 - https://www.acmicpc.net/problem/2775

 

 

접근 방법

 

2층 4호 --> 20 = 2층 3호 + 1층 4호 ( 노랑 네모들의 합)

1층 4호 --> 10 = 1층 3호 + 0층 4호 ( 초록 세모들의 합)

 

--> 재귀로 해결 가능

종료 조건 : 0층 or 1호

- 1호일 때 모든 값은 1

- 0층일 때 모든 값은 호수

 

def resident(k, n, apart):
    # 종료 조건: 0층이거나 1호일 때
    if n == 1:
        return 1
    if k == 0:
        return n

    return resident(k - 1, n) + resident(k, n - 1)

 

---

코드

 

- 처음에 Pypy3 통과 / Python3 시간 초과

 

def resident(k, n):
    # 종료 조건: 0층이거나 1호일 때
    if n == 1:
        return 1
    if k == 0:
        return n
    return resident(k-1, n) + resident(k, n-1)


T = int(input())
for i in range(T):
    k = int(input())
    n = int(input())
    print(resident(k, n))

 

- 최종 코드

: 재귀로 돌아가면서 이전 값을 변수 apart에 저장해줌

n <= 14이기 때문에 리스트 안에 n개의 딕셔너리를 만들어서 key 값을 k(층수)로 하여 더한 값 저장

 

 

 

#k층 n호
def resident(k, n, apart):
    # 종료 조건: 0층이거나 1호일 때
    if n == 1:
        return 1
    if k == 0:
        return n
    if k not in apart[n].keys():
        apart[n][k] = resident(k - 1, n, apart) + resident(k, n - 1, apart)

    return apart[n][k]

apart = [{} for i in range(15)]

T = int(input())
for i in range(T):
    k = int(input())
    n = int(input())
    print(resident(k, n, apart))

 

 

---

 

알고리즘 스터디 - 노션 기록

 

알고리즘 스터디