[BOJ] 10844: 쉬운 계단 수 (Python)

문제 링크

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

풀이 전략

Dynamic Programming

⏰ 29분 ⏰

규칙을 찾아 점화식을 구하면 Bottom-up 방식으로 쉽게 풀 수 있는 문제입니다.
다만 저같은 경우 점화식을 구하는 데 상당한 애를 먹었습니다..

끝자리가 3인 수를 만든다고 할 때, 전단계의 끝자리 숫자는 2여나 4여야 합니다. 따라서 전단계에서 끝자리가 2였던 수의 갯수와 끝자리가 4였던 수의 갯수를 더하면 끝자리가 3인 수를 만들 수 있는 것이죠.

이를 일반화시키면

• $i$ 단계에서 끝자리가 $k(0<k<9)$인 수의 갯수는, $i-1$ 번째 단게에서 끝자리가 $k-1$, $k+1$ 인 수의 갯수의 합과 같다.
• $i$ 단게에서 끝자리가 $0$, $9$ 인 수는, $i-1$번째 단계에서 끝자리가 각각 $1$, $8$ 인 수의 갯수의 합과 같다

고 할 수 있습니다. 이 로직을

이차원 dp 배열을 만들어 행에는 n (입력받은 자릿수), 열에는 0~9까지 숫자 중 각 끝자리가 몇 개씩 들어가있는지를 입력하는 방법을 통해 구현했습니다.

구현

if __name__ == "__main__":
    n = int(input())
    dp = [[0]*10 for _ in range(n)]
    
    # 첫 번째 단계 초기화
    dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    
    # 끝자리 수 갯수 구하기
    for i in range(1, n):
    	# 0 은 전단계 1에서만 생성되므로
        dp[i][0] = dp[i-1][1]
        for j in range(1, 9):
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
        
        # 9는 전단계 8에서만 생성되므로
        dp[i][9] = dp[i-1][8]
    
    print(sum(dp[n-1])%1000000000)

삽질

Dynamic Programming를 써서 풀어야 한다는 것은 문제를 보자 마자 알았지만, 점화식을 제대로 만드는 데 엄청난 시행착오를 겪었습니다.

애초에 원리를 생각해 보았으면 바로 점화식을 구할 수 있었을 텐데.. 그래도 이렇게 머리 박으면서 하는 과정이 실력 향상에 도움이 될 꺼라 믿습니다! (제발!)