10844_쉬운계단수

문제는 더보기!

 

문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 복사

1

예제 출력 1 복사

9

예제 입력 2 복사

2

예제 출력 2 복사

17

 

처음에는 100의 자리니까 리스트를 100개를 만들어서 값을 하나씩 채워나가면 되지 않을까? 라고 생각했다.

 

직접 머리로 생각하는건 3번째정도까지 가능했는데, 고민하다보니 결국 값을 관리해주는건 끝이 0일때와 9일때라고 생각했다. 나머지는 모두 2배수씩 늘어나지만, 0과 9 일때는 갈 방향이 한곳밖에 없기 때문이다.

 

그래서 리스트에 정보를 2개로 나누어서 0과 9로된 수의 개수를 같이 넘겨주면 되지 않을까란 생각이 들었다. 이러면 두번째 문제가 발생하게 된다. 0과 9로된 수읙 개수를 구하는 문제가 은근 복잡했던 것이다.

 

그래서 이번에는 각 자리에 오는 개수를 한번 나열해봤다.

 

0  1  1  1  1  1  1  1  1  1
1  1  2  2  2  2  2  2  2  1
1  3  3  4  4  4  4  4  3  2

 

 

보니까 위의 라인에서 대각선의 합이 아래배열로 오는것을 알 수 있다.

 

예를들어 2번째줄의 2번째1 은 1번째줄의 1번째 0 과 3번째 1 이 합한것이다.

 

 

이렇게 규칙을 발견하고 보니 이게 동적계획법이란 생각이 들었다. 계단에서 갈 방향이 2곳밖에 없기에 그곳까지의 최대값을 계속 더해가면 되었던 것이다. 

 

여태 동적계획법을 공부하고 있는데 아직도 갈피를 잘 못잡은 것 같다 ㅠㅠ

 

N = int(input())

lst = [ [0 for i in range(10)] for j in range(101) ]

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

for i in range(2,N+1):
    for j in range(10):
        if j ==0:
            lst[i][j] = lst[i-1][1]
        elif j == 9:
            lst[i][j] = lst[i-1][8]
        else:
            lst[i][j] = lst[i-1][j+1] + lst[i-1][j-1]


print(sum(lst[N]) % 1000000000)