[Backjoon] 쉬운 계단 수

백준 18044번 쉬운 계단 수 문제는 전형적인 백트래킹, 동적계획법 문제였다. 처음 문제를 접했을 때 당황했지만, 천천히 의사코드로 먼저 로직을 구성하고 나서는 어렵지 않게 풀이할 수 있었다. 하향식으로 문제를 풀었지만 상향식 해결법으로 풀이하는 고수들도 많다. 의사코드를 적어놔서 독자 여러분들도 어렵지 않게 로직을 이해할 수 있을 거라고 생각한다.

 

import sys

def find_step_number(length, last_num, container, cache):

    # 컨테이너 길이가 N이라면
    if length == 0:
        return 1

    if cache[length][last_num] != -1:
        return cache[length][last_num]

    # 숫자 0-9까지 반복
    count = 0
    for num in range(0, 10):
        # 컨테이너가 비어있고 숫자가 0이라면
        if len(container) == 0 and num == 0:
            continue

        # 지금 숫자가 컨테이너 이전 숫자와의 차이가 1이라면
        if len(container) == 0 or abs(num - container[-1]) == 1:
            # 숫자 삽입
            container.append(num)
            # 재귀호출
            count += find_step_number(length - 1, num, container, cache)
            # 숫자 빼기
            container.pop()

    cache[length][last_num] = count
    return count

if __name__ == "__main__":
    length = int(sys.stdin.readline())
    cache = [ [-1 for _ in range(10)] for _ in range(length + 1)]
    count = find_step_number(length, 0, [], cache)
    print(count % 1000000000)