[Python] 백준 10844번_쉬운 계단 수

문제 

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

10844번: 쉬운 계단 수

특이점

1. 계단수의 개념: 앞뒤 숫자와 차이가 1이나는 수들의 연속
2. 맨 앞 숫자로 0이 오는건 불가능하지만, 중간이나 끝에 0이 위치하는 것은 가능하다.
3. input은 계단의 길이, 즉 나열하는 숫자의 개수이다. output은 길이에 따라 가능한 경우의 수이다. 

코드

import sys

num = int(sys.stdin.readline())
#계단 수 담을 2차원 배열 dp[0~num][0~9] 생성
dp=[[0] * 10 for i in range(num+1)]
#dp[0]=[0,0,0,0,0,0,0,0,0,0]로 두고, 계단 길이 1인 경우 세팅
dp[1] = [0,1,1,1,1,1,1,1,1,1]

#나머지 길이인 경우 규칙 적용
for i in range(2, num+1):
    #0, 9 로 끝나는 경우 (예외 적용) - dp[i][j] = 0 + dp[i-1][j+1 or j-1]
    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]

#길이가 n일때 경우의 수를 sum으로 구하고, 1,000,000,000으로 나눈 나머지 출력
print(sum(dp[num])%10**9)

풀이 

• 이차원 배열을 이용해서 푸는 문제이다.
  • 이차원 배열 dp[i][j]에서, i는 계단의 길이(=num)를, j는 케이스에서 마지막에 오는 숫자를 의미한다.
  • 예를 들어, dp[2][4] => 길이가 2인 계단 수의 집합 중, 4로 끝나는 O - 4 인 경우의 수가 값으로 들어간다.
• 역가지치기 방식으로 값을 구해나간다고 볼 수 있겠다.
  
  • 결국 최종적으로 구하려는 길이가 n인 계단수의 개수는, 그 전까지의 계단수들의 누적이기 때문이다.
  • 4로 끝나는 계단수의 앞에 올 수 있는 숫자는 3과 5이다.
  • 즉, [   ] - 4 의 개수 == 어찌어찌 1~9에서 시작해서, 3까지 도달하는 수 + ~~어찌어찌 5까지 도달하는 수 이렇게 볼 수 있다는 것.
  • 반대로 생각하면, 4로 끝나는 계단수의 개수는 3으로 끝나는 계단수의 개수 + 5로 끝나는 계단수의 개수 로 구할 수 있다.

          ⇒ dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 도출

• 예외 경우))) j = 0, 9 일때  
  • j == 0 의 경우, -1(0-1)로 끝나는 계단수는 존재할 수 없다. → 1로 끝나는 계단 수만 더함. 즉 그대로 내려온다. 
  • j == 9 의 경우, 반대로 10(9+1)로 끝나는 계단수가 존재 불가능 → 8로 끝나는 계단수 개수가 그대로 내려온다.

 

다른 풀이 

 출처: https://www.acmicpc.net/source/17767811

n = int(input())

DP = [[0]*10 for i in range(101)]
DP[1] = [0,1,1,1,1,1,1,1,1,1]

for i in range(2,n+1):
    for j in range(10):
        if j == 0:
            DP[i][j] = DP[i-1][j+1]
        elif j == 9:
            DP[i][j] = DP[i-1][j-1]
        else:
            DP[i][j] = DP[i-1][j+1] + DP[i-1][j-1]
result = 0
for i in range(0,10):
    result += DP[n][i]

print(result%1000000000)

→ 입력값이 100 이하인 것을 이용해 처음부터 dp[0~100][0~9]인 2차원 배열을 완성했다. 

• 또한 range(10)으로 전체에 대해 for문을 돌리되, 예외경우인 0, 9에 대해서는 if-elif 분기문을 이용해 처리했다.  
• 10**9 대신 1000000000으로 나눠주는게 속도가 더 빠르다.