[맛있는물회] <백준 알고리즘> 10844번 "쉬운 계단 수"

문제 조건

---

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

Input

---

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

 

Output

---

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

생각한 아이디어

---

처음에 당연히 쉬운 점화식 DP 문제겠거니 하고 접근했다.

어라 규칙이 쉽네? 하고

arr[i] = (arr[i-1]-T) * 2 + T

이렇게 잡고 풀었다.

답이 나왔다.

 

그런데 틀렸다 ㅎㅎㅎ

그렇게 쉬운문제가 아니었던 것이다.

나는 T 부분이 규칙성이 있는 줄 알았는데 규칙이 없었다.

 

뒤에서 부터 접근하면 답이 나온다.!!

끝나는 자리수
IDX     0 1 2 3 4 5 6 7 8 9

1       0 1 1 1 1 1 1 1 1 1
2       1 1 2 2 2 2 2 2 2 1
3       1 3 3 4 4 4 4 4 3 2
4       3 4 7 7 8 8 8 7 6 3
...

즉, 1자리수에서는 모두 하나밖에없다.
2자리 수에서 0으로 끝나는 수는 1 0 으로 하나밖에없다. 1은 21로 하나밖에없다. 0으로 시작할 수가 없기때문.
3자리 수에서는 0으로 끝나는 수는 2 1 0 하나 뿐이다. 1은 1 2 1, 3 2 1, 1 0 1 이렇게 3가지다. 
그렇게 3자리수까지 쭉 적어내려가면 규칙이 나온다.

구하고 싶은 자리의 좌측상단 값과 우측상단 값을 더하면 나온다.

식이 나왔으므로 점화식을 세우고 DP 로 풀면 된다.

0과 9로 끝이 나는 경우는 따로 
dp[i][j] = dp[i-1][j+1] #0
dp[i][j] = dp[i-1][j-1] #9

2~8으로 끝이 나는 경우는 
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

로 계산하면 된다.

 

나는 시작점에서부터 1~9를 두고 시작했다. 그런데 답을 구하기 위해서는 뒤에서부터 시작해야했다. 발상의 전환도 알고리즘 문제 풀이에 꽤 중요한 것 같다. 

 

소스코드

#10844
#2차원 리스트 선언하고싶을때 dp.append([])이렇게 할 수 있음
N = int(input())

dp = list()
dp.append([0,1,1,1,1,1,1,1,1,1])

for j in range(1,N):
    dp.append([])
    dp[j].append(dp[j-1][1])#0
    for i in range(1,9):
        value = dp[j-1][i-1] + dp[j-1][i+1]
        dp[j].append(value)
    
    dp[j].append(dp[j-1][8])#9
sum = 0
for k in range(0,10):
    sum += dp[N-1][k]

print(sum%1000000000)

 

*파이썬 문법 정리