[Python] 백준 #10844- 쉬운 계단 수[Try_again]

문제

---

10844번: 쉬운 계단 수

코드

---

Another answer

from sys import stdin

n = int(stdin.readline())
stairs = [[0] * 10 for _ in range(n + 1)]
stairs[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, n + 1):
    # 계단 수가 0으로 끝나는 경우
    stairs[i][0] = stairs[i - 1][1]
    # 계단 수가 9로 끝나는 경우
    stairs[i][9] = stairs[i - 1][8]
    # 계단 수가 1~8로 끝나는 경우
    for j in range(1, 9):
        stairs[i][j] = stairs[i - 1][j - 1] + stairs[i - 1][j + 1]
print(sum(stairs[n]) % 1000000000)

 

풀이

---

우선 나는 이 문제를 못풀어서 다른사람의 코드를 가져왔다. 맨처음에 나는 저번에 알고리즘에 글을 작성했던 두가지 방법중 top-down방법을 이용해서 재귀를 사용해서 풀었다. 그런데 그 때 경고했듯이 시간초과가 나와서 실패했다. 알고리즘 자체가 맞았는지 틀렸는지도 모르겠다. 그래서 두번째로는 질문글들을 참조해서 이차원배열을 이용해서 풀어보려고했다. dp[i][j]로 배열을 만들어서 i를 자릿수,j를 시작숫자로 정해놓고 문제를 풀어보려고 했으나 규칙이 보이지않았다. 인터넷을 뒤져보니 i는 자릿수가 맞고, j를 끝에오는 숫자로 둬야 규칙이 보인다는 사실을 알아냈다. dp[i][j + 1]를 j로 끝나는 i자릿수의 계단 수로 생각하면 2자릿수의 5로 끝나는 계단의 수를 배열에 넣으려면 dp[2][6]에 넣으면 된다. 왜 끝에 오는 숫자로 j를 정했냐면 끝이 5로 끝나는 dp배열은 끝이 4나 6으로 끝나는 수 뒤에 5를 붙인 것과 같다. 따라서 아래 식을 점화식으로 세울 수 있다. 이 때 예외는 끝이 0이거나 9일때는 두가지가 아니라 1에 붙이거나 8에 붙이는 하나씩 밖에 안나오므로 예외처리를 따로 해주면 된다. 

dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]