[알고리즘 일기] 42. 출근하는 방법2

문제 42. (2021-06-11)

출근하는 방법2

영훈이는 출근할 때 계단을 통해 사무실로 가는데요. 급할 때는 두 계단씩 올라가고 여유 있을 때는 한 계단씩 올라갑니다. 결국 계단을 오를 수 있는 모든 방법으로 계단을 올라갔는데요.

이제 다르게 계단을 올라갈 수는 없을까 고민하던 영훈이는 특이한 방법으로 계단을 오르려고 합니다.

가령 계단을 한 번에 1, 2, 4 칸씩 올라가 보는 건데요. 예를 들어서 계단을 4개를 올라가야 되면:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
4

총 5개 방법이 있네요.

함수 staircase는 파라미터로 총 계단 수 n 그리고 한 번에 올라갈 수 있는 계단 수를 possible_possible_steps로 받고, 올라갈 수 있는 방법의 수를 효율적으로 찾아서 리턴합니다.

그러니까 n이 3, possible_possible_steps 가 [1, 2, 3]이면, 계단 총 3칸을 1, 2, 3칸씩 갈 수 있을 때 오르는 방법의 수를 수하는 거죠. 단, possible_possible_steps에는 항상 1이 포함된다고 가정합니다.

❧ 테스트 셋

def staircase(stairs, possible_steps):
    # Code

# Test
print(staircase(5, [1, 2, 3]))
print(staircase(6, [1, 2, 3]))
print(staircase(7, [1, 2, 4]))
print(staircase(8, [1, 3, 5]))

❧ 출력 예시

13 
24 
31 
19

---

❧ 정답

# 높이 n개의 계단을 올라가는 방법을 리턴
def staircase(stairs, possible_steps):
    result = 0
    # 계단 개수가 0 또는 1인 경우, 올라가는 방법 : 1
    if stairs < 2:
        return 1
    # n번 계단 전까지의 부분 문제 해결을 위해 for문 수행
    for i in range(len(possible_steps)):
        if (stairs >= possible_steps[i]):
            result += staircase(stairs-possible_steps[i], possible_steps)
    return result

print(staircase(5, [1, 2, 3]))
print(staircase(6, [1, 2, 3]))
print(staircase(7, [1, 2, 4]))
print(staircase(8, [1, 3, 5]))

1️⃣ 최적 부분 구조 있음

return (n-1) + (n-2) …

2️⃣ 각 (n-1), (n-2) 단계들에서 겹치는 부분 O

→ 동적 계획법 활용 가능