S1 10844. 쉬운 계단 수

문제 보기 :  10844번: 쉬운 계단 수

---

문제

• 정답률 : 30%

---

작성 코드 & 풀이 과정 코멘트

longg = int(input())

from collections import deque
answer = 0

start = [str(i) for i in range(1,10)]
start = deque(start)
while start:
    st = start.popleft()
    if len(st)==longg:
        answer += 1
    elif int(st[-1]) == 0: #10
        start.append(st+"1")
    elif int(st[-1]) == 9:
        start.append(st+"8")
    else:
        start.append(st+ str(int(st[-1])+1))
        start.append(st+ str(int(st[-1])-1))

print(answer)

이건 시간초과가 발생한 답안이다.
단순히 숫자를 이어붙이고 그 숫자의 길이가 longg과 같으면 제거하는 것으로 짰지만 역시나 시간초과가 발생했다.
그래도 이걸로 힌트를 얻었다. 

longg==1 : {'0': [], '1': ['1'], '2': ['2'], '3': ['3'], '4': ['4'], '5': ['5'], '6': ['6'], '7': ['7'], '8': ['8'], '9': ['9']}
longg==2 :
{'0': [], '1': ['12', '10'], '2': ['23', '21'], '3': ['34', '32'], '4': ['45', '43'], '5': ['56', '54'],
'6': ['67', '65'], '7': ['78', '76'], '8': ['89', '87'], '9': ['98']}
longg==3 :
{'0': [], '1': ['123', '121', '101'], '2': ['234', '232', '212', '210'], '3': ['345', '343', '323', '321'],
'4': ['456', '454', '434', '432'], '5': ['567', '565', '545', '543'], '6': ['678', '676', '656', '654'],
'7': ['789', '787', '767', '765'], '8': ['898', '878', '876'], '9': ['989', '987']}

이렇게 흘러가는데, 잘 보면 이전 값에 따라 longg이 1만큼 클 때 0,9인 경우를 제외하면 2배씩 늘어난다는 걸 볼 수 있다.

이걸 활용해서 리스트로 간단하게 코드를 짰다.

longg = int(input())

from collections import deque
answer = [[0]*10 for i in range(longg)]
answer[0] = [1]*10 #[1,1,1,1,1,1,1,1,1]
answer[0][0] = 0

for i in range(1,longg):
    for j in range(10):
        if j == 0: #0
            answer[i][1] +=answer[i-1][0]
        elif j == 9: #9
            answer[i][8] += answer[i-1][9]
        else:
            answer[i][j+1] += answer[i-1][j]
            answer[i][j-1] += answer[i-1][j]

print(sum(answer[-1])%1000000000)

시작점이 0-9일 때마다 달라지는 값을 리스트에 업데이트 시키는 알고리즘으로 해결했다.

answer는 10칸으로,
longg == 1이면 answer[0]을 보면 되는데 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]이고, 합은 9다.
longg == 2이면 answer[1]은 [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]이다. 답을 구하라 하면, 합은 17이다.
longg == 3이면 answer[2]은 [1, 3, 3, 4, 4, 4, 4, 4, 3, 2]이고 답은 32다.