[알고리즘][Python] 백준(BOJ) 10844 쉬운 계단 수_파이썬

DP

10844 쉬운 계단 수    www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

 

풀이 1

<내용>

• 계단 수의 경우 n = 1 일 때는 1 - 9까지 모두 가능하다.
• n = 2 일 때는 1 뒤에는 0 또는 2가, 2 뒤에는 1 또는 3이, ..., 8 뒤에는 7 또는 9가, 9 뒤에는 8만 올 수 있다.
• 이런 규칙이 반복되는데 n = 3에서부터 나오는 0 뒤에는 1만 올 수 있다.
• 규칙을 만들면, 0 뒤에는 1만, 9 뒤에는 8만, 1 - 8 뒤에는 (해당 숫자 - 1) 또는 (해당 숫자 + 1)이 올 수 있다.
• 위의 규칙을 이용해서 개수를 세면 된다.
• dp에 초기값이 0인 2차원 배열을 저장한다.
  • dp [n+1][10]의 형태이다.
• 위의 규칙대로 for문을 돌면서 개수를 저장한다.
• 마지막에 출력 전에는 반드시 1000000000으로 나눈 나머지를 출력하는 것을 잊지 않고 한다.

 

 

 

<코드>

n = int(input())

dp = [[0 for _ in range(10)] for _ in range(n+1)]

for i in range(1, n+1):
    if i == 1:
        dp[i] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    else:
        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]
                
res = sum(dp[n]) % 1000000000
print(res)

 

 

 

 

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 계단 수의 경우 n = 1 일 때는 1 - 9까지 모두 가능하다.
• n = 2 일 때는 1 뒤에는 0 또는 2가, 2 뒤에는 1 또는 3이, ..., 8 뒤에는 7 또는 9가, 9 뒤에는 8만 올 수 있다.
• 이런 규칙이 반복되는데 n = 3에서부터 나오는 0 뒤에는 1만 올 수 있다.
• 규칙을 만들면, 0 뒤에는 1만, 9 뒤에는 8만, 1 - 8 뒤에는 (해당 숫자 - 1) 또는 (해당 숫자 + 1)이 올 수 있다.
• 위의 규칙을 이용해서 개수를 세면 된다.
• 위의 코드와 다르게 2차원 배열로 저장하지 않고 1차원 배열로 저장한다.
• n번째에 맞는 1차원 배열을 (n-1)번째 배열을 이용하여 기존 배열이 아닌 다른 배열에 저장하고 기존 배열에 저장하는 방법이다.
• 위와 마찬가지로 1000000000으로 나눈 나머지를 출력해야 하는 것을 잊으면 안 된다.

 

 

 

 

<코드>

n = int(input())
d = {}
for i in range(10):
    if i == 0:
        d[i] = 0
    else:
        d[i] = 1
        
for i in range(2, n+1):
    g = {}
    for num in range(10):
        if num == 0:
            if num+1 in g:
                g[num+1] += d[num]
            else:
                g[num+1] = d[num]
        elif num == 9:
            if num-1 in g:
                g[num-1] += d[num]
            else:
                g[num-1] = d[num]
        else:
            if num+1 in g:
                g[num+1] += d[num]
            else:
                g[num+1] = d[num]
            if num-1 in g:
                g[num-1] += d[num]
            else:
                g[num-1] = d[num]
    d = g

res = sum(d.values()) % 1000000000
print(res)