[알고리즘] 코드잇 - 출근하는 방법2(Python)

설명

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

 

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

 

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

 

- 1, 1, 1, 1

- 2, 1, 1

- 1, 2, 1

- 1, 1, 2

- 2, 2

- 4

총 6개 방법이 있네요.

 

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

 

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

 

힌트1

계단의 높이가 4, 그리고 매번 오를 수 있는 계단 수는 1,2,3 이라고 생각해 봅시다.

- 0 -> 1 ->4

- 0 -> 1 ->2 ->4

- 0 ->2 ->4

- 0 ->1 ->3 ->4

- 0 ->1 ->2 ->3 ->4

- 0 ->2 ->3 ->4

-0 ->3 ->4

오를 수 있는 계단의 수는 1,2,3이기 때문에 4번 계단으로 가기 위해서는 결국 1,2,3번 계단에서 올라가야합니다.

 

이걸 일반화해볼까요?

 

힌트2

n번 계단으로 가기 위해서는 n-1, n-2, n-3번 계단에서 올라가야합니다.

 

이걸 코드로 표현해볼까요?

 

힌트3

수학적으로 표현하면 staircase(n)은 staircase(n-1)+staircase(n-2)+staircase(n-3)로 표현이 가능하죠?

지금은 possible_steps가 [1,2,3]이지만 더 일반화하면 아래 코드처럼 됩니다.

# staircase(n)가 처음에 0이면
for step in possible_steps:
    # 수학적으로 아래와 같이 표현할 수 있습니다.
    # staircase(n) += staircase(n - step)
    # 이를 코드로 구현해 주세요.

힌트4

매번 오를 수 있는 계단 수가 1,2,3 일때, staircase(n)를 수학적으로 staircase(n-1)+staircase(n-2)+staircase(n-3)처럼 표현했습니다.

 

문제의 최적의 답을 구하는데 부분 문제의 최적의 답을 이용할 수 있군요. 이 문제는 최적 부분 구조 문제가 있습니다.

 

힌트5

이 문제에 중복되는 부분 문제도 있을까요?

 

중복되는 부분 문제가 있는지 확인하기 위해서 아래의경우를 살펴봅시다.

staircase(5) = staircase(4) + staircase(3) + staircase(2)

staircase(4), staircase(3) 와 staircase(2)를 각각 구해야 되죠?

 

staircase(4)를 구하려면 staircase(3),staircase(2), staircase(1)을 알아야되고요. 계속 부분 문제들을 구하다 보면 중복되는 부분 문제가 생기게 됩니다.

 

최적 부분 구조와 중복되는 부분 문제가 동시에 있군요.

 

힌트6

Dynamic Programming 접근법을 사용하면 중복되는 부분 문제들을 한 번씩만 계산해 주어서 효율적으로 문제를 풀 수 있겠죠?

리스트를 업데이트해 주면서 Tabulation 방식으로 문제를 풀어 주시면 됩니다

 

답안

 

# 높이 n개의 계단을 올라가는 방법을 리턴한다
def staircase(stairs, possible_steps):
    # 계단 높이가 0 이거나 1 이면 올라가는 방법은 한 가지밖에 없다
    number_of_ways = [1, 1]
    
    # 이 변수들을 업데이트해 주며 n 번째 계단을 오르는 방법의 수를 구한다.
    for height in range(2, stairs + 1):
        number_of_ways.append(0)

        for step in possible_steps:
            # 음수 계단 수는 존재하지 않기 때문에 무시합니다
            if height - step >= 0:
                number_of_ways[height] += number_of_ways[height - step]

    return number_of_ways[stairs]

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