[백준 10844번] 쉬운 계단 수

백준 10844번 - 쉬운 계단 수 링크

문제

45656이란 수를 보자.

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

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

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

풀이

느낌이 안올 땐 손으로 그려보는 것 만큼 좋은 게 없다. 아이패드에 그려보았다.

되게 무식한 방법을 쓴 것 같지만, 정말 감이 바로왔다. 점화식까지 바로 세웠다.

근데 처음에 틀렸다. 코드 한줄 때문에 틀렸다!

틀린 코드

N = int(input())
dp = [[0 for _ in range(10)] for _ in range(N)]
dp[0][0] = 0
for i in range(1,10):
    dp[0][i] = 1

for i in range(1,N):
    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]

answer = 0
for i in range(10):
    answer += dp[N-1][i] % 1000000000

print(answer)

이 코드가 왜 틀렸냐 하면, 마지막에 answer값을 구할 때, answer값에다가 dp값을 모듈러한 값을 더하기 때문에, dp값은 10억보다 커질 수 있다.

고로 계산 순서가 틀려버린 것이다.

정답 코드

N = int(input())
dp = [[0 for _ in range(10)] for _ in range(N)]
dp[0][0] = 0
for i in range(1,10):
    dp[0][i] = 1

for i in range(1,N):
    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]

answer = 0
for i in range(10):
    answer = (answer + dp[N-1][i]) % 1000000000

print(answer)

이렇게 answer값에 더해주고 모듈러 하도록 바꿔주면 끝.
이번 문제는 제목 그대로 쉬웠다!