[알고리즘 일기] 40. 출근하는 방법1

문제 40. (2021-06-09)

출근하는 방법1

영훈이는 출근할 때 계단을 통해 사무실로 가는데요. 급할 때는 두 계단씩 올라가고 여유 있을 때는 한 계단씩 올라 갑니다. 어느 날 문득, 호기심이 생겼습니다. 한 계단 또는 두 계단씩 올라가서 끝까지 올라가는 방법은 총 몇 가지가 있을까요? 계단 4개를 올라간다고 가정하면, 이런 방법들이 있습니다.

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2

총 5개 방법이 있네요.

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

❧ 테스트 셋

def staircase(n):
    # Code

# Test
print(staircase(0))
print(staircase(6))
print(staircase(15))
print(staircase(25))
print(staircase(41))

❧ 출력 예시

1
13
987
121393

---

❧ 정답

Try 1 (Runtime ERROR)

def staircase(n):
    if (n <= 1):
        return 1
    return staircase(n - 1) + staircase(n - 2)

print(staircase(0))
print(staircase(6))
print(staircase(15))
print(staircase(25))
print(staircase(41))

Try 2

def staircase(n):
    case = [1]
    for i in range(1, n + 1):
        # case[0], case[1]은 1로 설정
        if i < 2:
            case.append(1)
        else:
            case.append(case[i - 1] + case[i - 2])
    return case[n]

print(staircase(0))
print(staircase(6))
print(staircase(15))
print(staircase(25))
print(staircase(41))

1️⃣ 처음에 재귀로 접근 -> 각 계단마다 2계단 밟는 경우를 생각함

└ 결국 피보나치 수열 원리와 동일

2️⃣ 재귀로 피보나치 수열 접근 시, 런타임 에러 발생

3️⃣ 반복문으로 재구현 (시간 복잡도 : O(n))