[Baekjoon 10844 / Python / 실버1] 쉬운 계단 수

문제

 

끔찍한 DP 문제이다.

문제를 고른 후에 알았는데 꽤 유명한 문제인 것 같다.

말 그대로 계단 수의 개수를 구하는 문제다. 점화식을 찾으면 쉽게 풀 수 있지만 그것을 찾는 게 매우 어렵다.

 

처음 접근 방식은, 1, 2, 3 자리수 계단 수 개수를 세서 그 증가폭에 대한 규칙을 찾으려 했지만 실패했다. 이 문제를 쉽게 풀기 위해선 2차원 배열을 사용하는 것과, 끝나는 숫자를 기준으로 생각하면 좀 더 쉽다.

 

예를 들어, N번째 자리에 숫자 1이 오기 위해선 N-1번째 숫자가 반드시 0 또는 2여야 한다.

즉, N-1번째에서 0으로 끝나는 숫자의 수와 2로 끝나는 숫자의 수를 합하면 N번째 자리에 1이 오는 계단수의 개수를 알 수가 있다.

 

표를 그려보면 좀 더 이해하기 쉽다.

 

1자리수는 9개

 

행은 자릿수(N), 열은 끝나는 수이다. 즉 N번째 자리에 해당 숫자가 들어간다는 뜻이다.

N이 1일 경우, 1~9까지 각각 1개씩의 계단수가 생긴다. 이것을 기본 틀로 잡고 간다. 0으로는 시작할 수 없으니 0은 없다.

N행의 값을 모두 더하면 총 9가 되므로, N이 1일 경우 계단수의 개수는 9개이다.

 

이전 자릿수 값을 이용한다

 

N이 2일 경우를 보자. 0부터 확인해 보면 값이 1이다. 왜 1일까?

2번째 자리에 0이 오기 위해서는 반드시 이전 값이 1 이어야 한다. 그 외의 경우는 없다. 그렇다면 이전 값이 1일 경우는 어떻게 확인하는가?

바로 윗 줄, N이 1일 경우를 보면 된다. N이 1이었을 경우 1로 끝난 경우가 1개뿐이므로, N이 2일 경우 0이 올 수 있는 경우의 수도 마찬가지로 1이다.

 

이번엔 2번째 자리에 1이 올 수 있는 경우를 보자. 1이다. 왜 1일까?

2번째 자리에 1이 오기 위해선 이전 자리에 반드시 0 또는 2가 와야 한다. 따라서 N이 1이었을 경우 0,2로 끝난 경우를 더해주면 된다.

바로 윗 줄 값을 확인해 보면, 0으로 끝난 경우는 0번이고 2로 끝난 경우는 1번이다. 이것을 더하면 1이 된다.

 

마지막으로 2번째 자리에 2가 올 수 있는 경우를 보자. 2이다.

2가 오려면 어떤 조건이 필요할까? 이전 자리에 반드시 1 또는 3이 와야 한다. 마찬가지로 윗줄에서 찾아서 더해준다.

1로 끝난 경우는 1번, 3으로 끝난 경우도 1번이다. 두개를 더해주면 2다.

 

이것을 점화식으로 세우면 이렇다.

N = 자릿수

i = 끝나는 수

dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1]

 

물론 이렇게 했을 경우 0 또는 9는 각각 이전, 이후 숫자가 없기 때문에 예외가 생긴다. 이 경우는 0이나 9일 경우에 대해서 예외 처리를 해주거나, 2차원 배열에 패딩값을 넣어주면 된다. 무슨 소리냐?

 

0일 경우 0-1번 값을 조회할 때 오류가 생기지 않도록 앞에 0 값을 가지는 열을 하나 추가한다.

9일 경우 9+1번 값을 조회할 때 오류가 생기지 않도록 뒤에 0값을 가지는 열을 하나 추가한다.

즉 2차원 배열을 만들 때 10의 크기가 아닌 12의 크기로 만들고, 처음과 끝에 0이라는 무의미한 값을 넣어두면 된다.

 

# 다이나믹 프로그래밍

import sys

input = sys.stdin.readline

N = int(input())

# 2차원 배열 생성

# 행 : 자릿수(N), 열 : 끝나는 숫자

dp = [[0] * 12 for _ in range(N + 1)]

for i in range(2, 11):

    dp[1][i] = 1

# 두자릿수부터 채운다

for i in range(2, N + 1):

    for j in range(1, 11):        

        dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

print(sum(dp[N]) % int(1e9))

 

늘 그렇지만 DP나 그리디 문제는 난이도에 비해 코드가 짧아 현타가 온다.

출력할 땐 1e9(10억)으로 나눠서 출력해주면 된다.

 

 

결과