백준 10844번 <쉬운 계단 수>

백준 알고리즘 10844번

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

---

10844번

인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하여라.

 

입력으로 N이 주어진다.

 

출력으로 계단수의 개수를 1,000,000,000으로 나눈 나머지를 출력한다.

---

문제 해결

stairN 배열은 이차원 배열로 각 길이에서 계단 수의 개수를 의미한다.

 

stairN[i][j] : 길이가 i이고 j를 포함하는 계단 수의 개수이다.

계단 수는 인접한 모든 자리의 차이가 1이기 때문에 stairN[i][j] = stairN[i-1][j-1] + stairN[i-1][j+1] 이다.

길이가 i-1이고 j-1로 끝나는 수에 j를 붙이거나 길이가 i-1이고 j+1로 끝나는 수에 j를 붙이면 된다.

이때, j가 0인 경우와 9인 경우를 예외처리 해줘야 하는데 0에서 -1을 할 수 없고 9에 +1을 할 수 없기 때문이다. 

 

---

코드

def main():
    n = int(input())
    stairN = [[0 for _ in range(10)] for _ in range(n+1)]
    stairN[1] = [0,1,1,1,1,1,1,1,1,1]

    for i in range(2,n+1):
        for j in range(10):
            temp = stairN[i-1][j]
            if j == 0:
                stairN[i][j+1]+=temp
            elif j == 9:
                stairN[i][j-1] += temp
            else:
                stairN[i][j+1] += temp
                stairN[i][j-1] += temp

    result = 0
    for i in stairN[n]:
        result += i
    result = result % 1000000000
    print(result)


main()

---

결과

---