[ 2023-03-20🐊 TIL ]

백준 10844번

import sys

input = sys.stdin.readline

n = int(input())

li = [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]] + \ #1의 자리수는 각각 계단수가 자기자신밖에없음
    [[0 for _ in range(10)] for _ in range(n-1)]

for i in range(1, n):
    for j in range(10):
        if j == 0:
            li[i][j] = li[i-1][1] #0로 1의 자리 수는 계단수가 1로 끝나는 수 밖에 없음
        elif j == 9:
            li[i][j] = li[i-1][8] #9로 1의 자리 수는 계단수가 8로 끝나는 수 밖에 없음
        else:
        	#그 외 수는 계단수가 2개씩 존재
            li[i][j] = li[i-1][j-1] + li[i-1][j+1]

print(sum(li[n-1]) % 1000000000)

처음에 풀었는데 너무 어지럽고 더럽게 풀어서..ㅋㅋㅋㅋㅋㅋ 메모리 초과가(따로 확인해보니 시간초과도 발생 ㅋㅋㅋ) 발생하였다.. 이걸 DP라고 부를 수 있나 모르겠다.

결국 구글의 도움을 받아서 문제를 해결하였습니다..ㅠ

내가 쓴 코드의 장점은 입력으로 들어온 자릿수의 계단수가 어떤것이 있는지 확인 가능하다는거?
아래에 코드가 제가 처음에 작성한 코드입니다. 확인해보니..한 n이 20일 때까지는 확인 가능합니다 ㅋㅋㅋ

import sys

input = sys.stdin.readline

n = int(input())

li = [str(i) for i in range(10)]
result = li
if n == 1:
    print(9)
else:
    start = 1
    for c in range(n-1):
        end = len(result)
        re = []
        for i in range(start, end):
            check = int(result[i][c])
            if (check - 1) == -1:
                re.append(result[i] + str(check + 1))
            elif (check + 1) == 10:
                re.append(result[i] + str(check - 1))
            else:
                re.append(result[i] + str(check + 1))
                re.append(result[i] + str(check - 1))
        start = end
        result += re
    print(len(re) % 1000000000)