문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

www.acmicpc.net/problem/10844

입력

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

출력

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

과정

지금까지 풀었던 문제들처럼 1부터 답을 차근차근 구하면 되지 않을까 해서 1부터 답을 구해보았다.

  • 1의 경우 9개
  • 2의 경우 17개
  • 3의 경우 32개

4부터는 구하지 않고, 점화식을

dp[n] = dp[n-1]*2 - (n-1)

이렇게 가정해보았으나 답이 아니었다.

생각해보다가 오래 끌기보다는 빨리 답을 보는 게 낫겠다 싶어서 처음으로 문제를 해결하지 못하고 답을 찾아봤다.

최종 코드

  • 마지막 자리수가 0인 경우 뒤에 올 수 있는 수는 1로 한 개이다.
  • 마지막 자리수가 9인 경우도 뒤에 올 수 있는 수는 8로 한 개이다.
  • 마지막 자리수가 1-8인 경우는 뒤에 올 수 있는 수가 2개씩 존재한다.
/ 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
자리수(4) 3 4 7 7 8 8 8 7 6 3

이러한 규칙을 참고해서 자리수 4까지 표를 만들어보면 대각선 위의 숫자 두 개를 더해서 표를 채울 수 있다는 것을 알 수 있다. 즉 아래와 같이 정리할 수 있다.

  • arr[i][0]인 경우 arr[i][0] = arr[i-1][1]
  • arr[i][9]인 경우 arr[i][9] = arr[i-1][8]
  • arr[i][1-8]인 경우 arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1]
import copy

N = int(input())

arr = [[0]*10 for i in range(2)]
arr[0] = [0,1,1,1,1,1,1,1,1,1]

for i in range(1, N):
    for j in range(10):
        if j == 0:
            arr[1][0] = arr[0][1]
        elif j == 9:
            arr[1][9] = arr[0][8]
        else:
            arr[1][j] = arr[0][j-1]+arr[0][j+1]
    arr[0] = copy.deepcopy(arr[1])

print(sum(arr[0])%1000000000))

2*10 크기의 배열을 사용했는데, 여기서 주의할 점은 arr[0]에 arr[1]을 복사할 때 deepcopy를 사용해야 한다는 것이다. 그냥 =을 사용하거나 copy를 사용하면 주소도 똑같이 복사되어서 원하지 않는 결과를 얻을 수 있다. 다른 주소의 다른 개체를 만들 때에는 deepcopy를 사용하자!

참고 사이트