[코드잇] 출근하는 방법 2 python

출근하는 방법2.py

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


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


가령 계단을 한 번에 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이 포함된다고 가정합니다.





######솔직히 어떻게 맞춘건지도 모르겟다 ㅋㅋ.. 이게되네? 느낌으로 맞춤ㅋㅋㅋㅋㅋㅋㅋㅋ

나의 풀이

# 높이 n개의 계단을 올라가는 방법을 리턴한다
def staircase(stairs, possible_steps):

    dic ={}
    dic[0]=1
    dic[1]=1
    
    #일단은 출근하는 방법 1의 계산대로
    #dic[n] = dic[n-2]+dic[n-1]
    #의 확장개념으로
    #dic[n] = dic[n-list[0]]+dic[n-list[1]+.....dic[n-list[n]]으로 계산했다...
    #솔직히 왜 되는지는...모르겠다 ㅋ... 이해를 제대로 하자...
    for i in range(2,stairs+1):
        for j in range(0,len(possible_steps)):
            if i-possible_steps[j]>= 0 :
                if dic.get(i):
                    dic[i] += dic[i - possible_steps[j]]
                else:
                    dic[i] = dic[i - possible_steps[j]]


    return dic[stairs]


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


###풀이

힌트 1 :
계단의 높이가 44, 그리고 매번 오를 수 있는 계단 수는 11, 22, 33 라고 생각해봅시다.


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

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


이걸 일반화하면 어떻게 될까요?


힌트 2 :
nn 번 계단으로 가기 위해서는 n - 1n−1 번 n - 2n−2 번 n - 3n−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 :
매번 오를 수 있는 계단 수가 11, 22, 33일 때, 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]))

13
24
31
19

계단을 올라가는 방법이 잘 출력되는군요!


시간 복잡도

stairs가 n, possible_steps의 길이가 m이라고 할 때, staircase 함수는 n에 비례하는 반복문 안에 m에 비례하는 반복문 하나가 있죠?


그렇기 때문에 이 함수의 시간 복잡도는 O(mn)O(mn)입니다.