점화식도 규칙도 막 찾으려고 애썼는데 결국 못 찾구.. 구글링을 했다.. 아이디어는 2차원 배열! DP[자릿수][맨 뒷자리의 수] 형식으로 리스트를 만드는 것이다. 2차원 리스트를 활용해서 열심히 끄적이며 풀어보았다.
코드
import sys
input = sys.stdin.readline
N = int(input())
DP = [[0] * 10 for _ in range(N+1)] # DP[자릿수][맨 뒷자리의 수]
DP[1] = [1 for _ in range(10)]
DP[1][0] = 0 # 1자리의 수에는 0 없음
for i in range(2, N+1):
DP[i][0] = DP[i-1][1]
DP[i][9] = DP[i-1][8]
for j in range(1, 9):
DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]
print(sum(DP[N]) % 1000000000)- 겹치는 것 때문에 앞뒤로 붙이는 것 모두 고려하는 게 아니라 앞/뒤에 붙이는 것만 고려하면 된다.
- 또한 맨 뒤(맨 앞)가 0이면 1만 가능, 9면 8만 가능, 나머진 2개씩 가능하다.
- 그래서 DP를 활용하기 위해 1자리수인 것들은 미리 적어두었고, for문과 DP를 이용해서 나머지들을 채워넣었다.
- 앞서 말한 2가지를 고려해서 맨 뒤자리가 0/9일 때는 따로 적어두고 나머지는 for문으로 DP를 채워넣었다.
결과
- 2가지 고려해야 되는 점들은 알아냈는데.. 2차원은 생각도 못했어서 아쉽다.. 아직 코테는 멀었나 흑흑 너무 갇혀서 생각하지 말고 다양한 알고리즘 아이디어들을 떠올려서 문제를 풀어야겠다.
