[백준] 10844 쉬운 계단 수

---

 

45656과 같이 모든 자릿수가 1씩 차이나는 수를 계단 수라 정의하고, 주어진 N자리 수의 총 계단의 수를 파악하는 문제이다.

N의 수는 N-1의 1의 자리 수 +- 1을 1의 자리 수에 추가하는 규칙을 가지고 있다는 것을 발견하고 나열 하면 아래와 같이 나타난다.

 

N=1

1, 2, 3, 4, 5, 6, 7, 8, 9



N=2

10, 21, 32, 43, 54, 65, 76, 87, 98

12, 23, 34, 45, 56, 67, 78, 89

....

 

위와 같이 나열하다 보니 아래와 같은 점화식을 도출해 낼 수 있었다.

N = 짝수  2 * D[i-1] - (i-1)

N = 홀수  2 * (D[i-1] - (i-2))

 

하지만 적절한 점화식이 아니었고 다른 분의 풀이를 참고하였다. 

 

   1의 자리수
N   0  1  2  3  4  5  6  7  8  9

1   0  1  1  1  1  1  1  1  1  1

2   1  1  2  2  2  2  2  2  2  1  

3   1  3  3  4  4  4  4  4  3  2

...

 

위에서 말했듯이 N자리 계단 수는 N-1의 1의 자리 수 +- 1를 1의 자리에 추가한 결과이다. 각 1의 자리수 개수를 표로 나타내면 위와 같다.

 

점화식으로 나타내면 

 

D[n][0] = D[n-1][1]

D[n][9] = D[n-1][8]

D[n][i] = D[n-1][i-1] + D[n-1][i+1] 로 나타낼 수 있다.

 

 

소스 코드

from sys import stdin
readline = stdin.readline

MOD = 1000000000
def main():
    N = int(readline().strip())
    d = [[0] * 11 for _ in range(101)]

    for i in range(1, 10):
        d[1][i] = 1

    for i in range(2, N+1):
        d[i][0] = d[i-1][1]
        for j in range(10):
            d[i][j] = (d[i-1][j-1] + d[i-1][j+1]) % MOD

    print(sum(d[N]) % MOD)


if __name__=="__main__":
    main()

 

메모리를 줄이기 위해 슬라이딩 윈도우 기법도 사용 가능하다.

from sys import stdin
readline = stdin.readline

MOD = 1000000000
def main():
    N = int(readline().strip())
    d = [[0] * 11 for _ in range(2)]

    for i in range(1, 10):
        d[1][i] = 1

    ans = 9
    for i in range(2, N+1):
        ans = 0
        for j in range(10):
            d[i%2][j] = (d[(i-1)%2][j-1] + d[(i-1)%2][j+1]) % MOD
            ans += d[i%2][j] % MOD
    print(ans % MOD)


if __name__=="__main__":
    main()