[BOJ] 10844 쉬운 계단 수

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

10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

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

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

입력

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

풀이

DP문제는 항상 나에게 쥐약이다(나만 그런건가ㅠ). 항상 점화식을 생각해내야하는 부분에서 막히고는 한다. 뭔가 복잡하게 생각하게 되고 생각이 꼬이다 보니 기피하는 경향이 있었던 것 같다. 그러나 언제까지 도망칠 수는 없는법, 이제 본격적으로 매일 몇 문제씩 풀어보기로 했다. 일단 가장 웰노운이고 쉬운 문제들부터 풀려고 했다. 먼저 DP에 대해 기초라 하기도 애매한 실력이어서 사람들의 힌트 몇개를 얻어 DP 테이블을 설정하였다. 먼저 이 문제는 0~9까지 일의 자리 숫자에서 뻗어나가는 식으로 생각했기에 [101][10]인 배열을 선언하였다. 그 다음 바텀업 방식으로 생각하여 맨 처음에는 일의 자리 수에 1~9 총 9개 숫자가 있으므로 dp[1]의 0을 제외한(0으로 시작한 수는 계단수가 아니다) 각 인덱스에 해당하는 요소에 1씩 더해줬다. 여기서 숫자 중에 신경 써야 할 부분은 0과 9인데, 0은 인접한 수가 1밖에 없고, 9 또한 8밖에 없다. 그러므로 점화식을 세울 때 j가 9혹은 0일 시에는 인덱스 8, 1의 값만 가져와서 더해주고, 나머지 숫자는 자기보다 하나 작거나 큰 인덱스에 해당하는 값을 자기 자신에 더해주었다. 이 문제는 한 번 또 꼬았는데, N이 100까지이므로 오버플로우가 나올 가능성이 농후했다. 문제에서 또한 이를 인지해주었는데, 1,000,000,000으로 나눈 나머지값을 출력하라고 하였다. 다 더해주고 나중에 나머지를 구하면 오버플로우가 날 터이니, 0~9까지 스캔할 떄(j 두번째 반복문) 더해주는 과정이 끝나고 나면 바로 % 연산을 해주었다.(이에 대한 증명은 다른 블로그에 많이 다룰테니 여기선 다루지 않겠다). 마지막으로 모든 값을 구했으면 마지막에도 %연산을 한번 더 해주어야 한다((a+b)%c = (a%c+b%c)%c). dp[n]에 10개의 요소를 더해줄 때 오버플로우가 발생할 수 있으니 한개씩 더해주면서 %연산을 해준다.

n = int(input())
dp = [[0 for _ in range(10)]for _ in range(101)]
for i in range(1, 10):
  dp[1][i] = 1
for i in range(2, 101):
  for j in range(10):
    if j == 0:
      dp[i][j] += dp[i-1][1]
    elif j == 9:
      dp[i][j] += dp[i-1][8]
    else:
      dp[i][j] += dp[i-1][j-1] + dp[i-1][j+1] 
    dp[i][j] %= 1000000000
result = 0
for i in range(10):
  result = (result + dp[n][i]) %1000000000
print(result)