방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 dp로 해결할 수 있는 문제였습니다. n=3인 경우 32가지, n=4인 경우 61가지가 존재함을 알고,

9 -> 17 -> 32 -> 61로 규칙을 찾으려 했으나 실패했습니다.

다음과 같이 표를 그리면 규칙을 찾을 수 있었습니다.

 가로는 끝나는 수(0~9), 세로는 n(n>=1)입니다. 예를 들어서 빨간색으로 표시된 3의 경우 3자리 수 중 끝이 1로 끝나는 숫자를 말합니다.

101, 121, 321 총 3가지가 존재함을 알 수 있습니다.

표를 보면 규칙을 알 수 있는데 i, j(각각 행, 열 의미) j가 0이면 i-1행의 j+1을 가져오고, j가 9이면 i-1행의 j-1을 가져오고 그 외의 경우는 직전행의 좌측, 우측 열의 값을 합한 것을 가져옵니다. 이를 소스코드로 작성하면 다음과 같습니다.

소스코드

n = int(input())

dp = [[0] * 10 for _ in range(n)]
for j in range(1, 10):
  dp[0][j] = 1
for i in range(1, n):
  for j in range(10):
    if j == 0:
      dp[i][j] = dp[i-1][j+1]
    elif j == 9:
      dp[i][j] = dp[i-1][j-1]
    else:
      dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

ans = 0
for j in range(10):
  ans += dp[n-1][j]
print(ans % 1000000000)