코드

n = int(input())

# n이 1 ~ 100까지의 자연수이므로
# dp테이블을 미리 101만큼 생성
d = [[0 for i in range(10)] for j in range(101)]

# n = 1일 때의 DP 테이블 초기화
for i in range(1, 10):
    d[1][i] = 1
    
# i: 입력받을 n
for i in range(2, n+1):
    
    # j: 숫자 0~9까지
    for j in range(10):
        # 0, 9 일 때는 별도 처리
        
        # 0일 때 : 이전 까지의 dp테이블값 중 1의 값만 가지고 옴
        if j == 0:
            d[i][j] = d[i-1][1]
        # 9일 때 : 이전 까지의 dp테이블 값 중 8의 값만 가지고 옴
        elif j == 9:
            d[i][j] = d[i-1][8]
        else:
            d[i][j] = d[i-1][j-1] + d[i-1][j+1]
print(sum(d[n]) % 1000000000)

문제 해설

DP 문제.

n자리의 수가 주어질 때, 연속적인 숫자들이 1씩 차이가 나는 수의 개수를 구하라는 문제이다.

아래의 풀이를 보자.

URI

n자리 수가 주어질 때, 각 자리수를 이룰 수 있는 숫자는 당연히 0부터 9까지이며, 맨 첫자리가 0으로는 주어질 수 없다. 만약 어떠한 자리에 0이나 9가 주어진다면, 0에서 9는 이어지는 숫자가 아니므로 그 옆에 위치한 수는 각각 1 또는 8일 수 밖에 없다. 0이나 9가 아니라면, 당연히 앞과 뒤 숫자 총 2가지의 숫자가 주어질 수 있다. 즉, 자리수가 증가할 때 마다(n의 값이 1씩 증가할 때 마다) DP테이블의 값은 이전 DP테이블의 앞과 뒤의 숫자의 합으로 이루어진다. 따라서 DP테이블은 2차원으로 작성해야 한다.

이를 토대로 점화식을 세워보면 위 그림의 밑에 있는 파란색 글자가 되고, i가 0과 9일 때는 별도의 조건을 부여하여 문제를 해결하면 된다.

d[n][i]

  • n : 주어진 자리 수
  • i : 그 자리 수에 오는 숫자의 값

댓글남기기

참고