10844번. 쉬운 계단 수

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

 

 

 

이전까지 풀었던 단순하게 눈에 보이는 규칙 찾기로는 풀리지 않는 문제였다.

뭔가 전에 자릿수에서 그 다음 자릿수의 수들이 파생된다는 것은 알겠는데,

컴퓨터가 하는 일이므로 정확한 기준을 가지고 어떻게 파생이 되는지를 캐치했어야 했는데 그러지 못했다.

 

생각의 흐름은 다음과 같다. (잘못된 생각의 흐름이다)

 

1. 전에 풀었던 것처럼 규칙을 찾아야겠구나

2. 0은 0이고, 1일 때는 9이다. 그럼 2일 때는...(하나하나 만들어서 세어봄)

3. 자릿수가 3개인 수 중에서 계단 수를 만들어보면서 세는데, 자꾸 누락되는 게 생겼다.

4. 자릿수가 4개인 수 중에서 계단 수를 만들어보려고 했는데, 너무 양이 많아져서 이 방향이 맞는가 하고 의구심이 들었다.

5. 결국 3까지 만든 결과에서 점화식을 만들어서 풀었는데, 3까지는 적용되었지만 답은 아니었다.

 

문제는 수가 너무 커지는데 이를 무식하게 단순한 수열 규칙을 찾으려고 했던 것이었다.

수가 커지므로, 이를 분할해서 규칙을 찾았으면 좀더 정답에 접근할 수 있었을 것 같다.

 

정답의 아이디어는

자릿수가 N일 때 0으로 끝나는 계단 수, 1로 끝나는 계단 수, ....9로 끝나는 계단 수를 따로 찾는 것이다.

이를 표로 그려놓고 보면 규칙이 보인다.

양 대각선 위 방향을 더한 것이다. 0이나 9는 대각선 방향이 하나 밖에 없으므로 구현할 때는 if문으로 따로 나눠줘야 한다.

import sys

N = int(sys.stdin.readline())
cal = [[0]*10 for _ in range(N+1)]
cal[1] = [0,1,1,1,1,1,1,1,1,1]

for i in range(2, N+1):
    for lastNum in range(0, 10):  # 0부터 9까지
        if lastNum == 0:
            cal[i][lastNum] = cal[i-1][1]
        elif lastNum == 9:
            cal[i][9] = cal[i-1][8]
        else:
            cal[i][lastNum] = cal[i-1][lastNum-1] + cal[i-1][lastNum+1]

ret = 0
for i in range(10):
    ret += cal[N][i]

print(ret % 1000000000)