DP에 아직 익숙치 않음을 느낄 수 있었던 문제였다. 처음부터 무작정 개수를 헤아리려 했기 때문에 해법을 떠올리는데 오래 걸렸다.
이런 종류의 문제 해결은 이전 DP 문제들과 비슷한 양상을 보이는데, 유효한 경우의 값을 저장해두는 것이 매우 간단한 해결로 이어지는 것 같다.
RGB 거리, 포도주 시식 문제에서 보이는 바와 같이 빨, 파, 초를 어떤 집에서 칠할 경우 얻을 수 있는 최적의 해를 각각 계산하고, 몇 번째인가 포도주를 마실 경우 가능한 최적의 해를 마신경우, 마시지 않은 경우에 따라 각 각 계산해 저장하는 방식을 이용해왔다.
이번 문제의 해결 방식도 그와 유사하지만 완전히 같다고 확언하기는 힘든것 같다. 내 짧은 견해와 사유의 문제일 수도 있겠다.
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자.
0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
고민과정
처음엔 이전에 풀었던 01 타일의 초반 해결 방법처럼 길이가 N인 경우 N-1, N-2 등등 이전 길이 계단수들을 조사하여 어떤 계산식을 이용하면 답이 나올것이라 잘 못 된 기대를 해버렸다. 그래서 N = 1부터 일일이 N = 5까지 적어봤지만 개수가 너무 많아져버렸고, 어느 순간 난잡해진 연습지 지면에서 별 다른 해결책을 찾지 못했다.
그 후 며칠정도 딥러닝 기초 교육과 일상 생활을 하면서 틈틈이 이 문제가 생각났는데, 결국 샤워하다가 0~9 까지 저장하는 배열을 사용해도 N이 그리 크지 않으니 별 무리없이 동작할 것 같다는 생각이 들었다. 그리고 N = 1부터 1씩 증가할 때 계단수가 되는 양상이 이진 트리와 비슷한 형태라는 점을 감안하면 길이가 N인 계단수에서 0~9로 끝날 때를 각각 저장하는 2차원 배열에서 덧셈을 이용하여 간단히 계산이 될 것이라 생각이 들어서 코드를 작성했고 결국 해결했다.
아래는 내가 제출한 파이썬 코드이다.
import sys
tbl = [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
n = int(sys.stdin.readline())
for i in range(1, n) :
tbl.append([0] * 10)
tbl[i][0], tbl[i][9] = tbl[i-1][1], tbl[i-1][8]
for j in range(1, 9) :
tbl[i][j] = tbl[i-1][j-1] + tbl[i-1][j+1]
print(sum(tbl[n-1]) % (10**9))이번 문제에서도 시원하게 말은 못하지만, N의 길이 계단수를 구하기 위해서 N = 1부터 시작해서 바로 직전 길이 계단수 개수를 사용해 매우 쉽게 해결한다.
왜인지는 모르지만 자꾸 메모리 공간 사용을 줄여야 한다는 생각이 들어서 적극적으로 테이블을 사용하는 것이 저어되기도 한다. 앞으로 더 DP 문제를 해결하면서 빠르게 적용하는 연습이 필요할 것 같다.
