[BOJ] 10844번 쉬운 계단수 / 사용언어 : 파이썬(python)

※ 문제링크

10844번: 쉬운 계단 수

※ 관련개념

메모이제이션 - 위키백과, 우리 모두의 백과사전

※ 참고 사이트

[백준] 10844번(python 파이썬)

해당문제는 메모이제이션과 배열을 활용하여 푸는 문제였다. 문제이름은 쉬운 계단수인데 풀어보니 해결방법이 너무 어려웠다. 처음 생각했던 방법은 리스트로 숫자를 받아서 계속해서 갱신하여 푸는 방법이었는데, 답은 잘 나왔으나 시간초과로 실패했다. 해결방법을 고민해도 도저히 답이 나오지 않아 구글링을 통해 문제를 해결했는데, 내가 발견하지 못한 규칙이 존재했고, 해당 규칙을 파악하면 생각보다는 쉽게(?) 풀 수 있는 문제였다. 이번 문제를 풀면서 단순히 메모이제이션만 쓴다고 해서 효율적으로 코드를 작성할 수 없다는 것을 다시 알 수 있었으며, 부족한 부분을 확인할 수 있는 기회였던거 같다. 내가 실패했던 코드와 참고한 사이트의 코드는 아래와 같다.

 

# 단순 메모이제이션을 통해 푸는 방법 # 시간초과
N = int(input())
dp = [str(i) for i in range(1, 10)]
cnt = 1
while N > cnt:
    dp_next = []
    for i in range(len(dp)):
        if dp[i][-1] == '9':
            dp_next.append(dp[i][-1] + str(int(dp[i][-1]) - 1))
        elif dp[i][-1] == '0':
            dp_next.append(dp[i][-1] + str(int(dp[i][-1]) + 1))
        else:
            dp_next.append(dp[i][-1] + str(int(dp[i][-1]) + 1))
            dp_next.append(dp[i][-1] + str(int(dp[i][-1]) - 1))
    dp = dp_next[:]
    cnt += 1

print(len(dp) % 1000000000)

# 1~9까지의 숫자가 각각의 자릿수마다 얼마나 올수 있는지를 확인하여 푸는 방법 # 통과가능
N = int(input())
dp = [[0 for i in range(10)] for k in range(101)]
for i in range(1, 10):
    dp[1][i] = 1
for i in range(2, N + 1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i - 1][1]
        elif j == 9:
            dp[i][j] = dp[i - 1][8]
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
print(sum(dp[N]) % 1000000000)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.