[BOJ] 10844번: 쉬운 계단 수

https://www.acmicpc.net/

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

10844번: 쉬운 계단 수

 

처음에 생각했던 방식은 N이 1일 때 부터 시작해서 9, 17, 32,,,,순으로 개수가 증가하길래 dp[1] = 9로 정해두고

dp[N] = dp[N-1]*2 - N + 1 와 같은 식을 생각했다. 하지만 이렇게 코드를 작성했을 경우 틀렸습니다!가 표시,,,,

예를들어 N이 5일경우 내 식에 의하면 118이지만 답은 116이 나온다. 따라서 다른 코드를 생각했다.

 

N이 1일때,

0 은 0가지

1, 2, 3, 4, 5, 7=6, 7, 8, 9 모두 1가지이다.

 

N이 2일때,

뒤에 붙는 숫자를 기준으로 생각해보자.

만약 1이 붙는다면 1은 0과 1뒤에 붙을 수 있다. 하지만 0은 앞에 올수 없기때문에 이 경우 1가지이다.

만약 2가 붙는다면 2는 1과 3뒤에 붙을 수 있다. 따라서 2가지 이다.

만약 9가 붙는다면 9는 8뒤에 붙을 수 있다. 따라서 1가지 이다.

 

N이 3일때,

N이 2인 경우의 값을 사용해 구할 수 있다.

만약 1이 붙는다면 앞에는 1이 올 수 있다. 이는 N이 2일 때 1 앞에 올 수 있는 수의 개수가 된다. 

만약 2가 붙는다면 앞에는 1, 3이 올 수 있다. 이는 N이 2일 때 1앞에 올 수 있는 수의 개수와 3앞에 올 수 있는 수의 개수를 더한 가지수가 된다.

 

즉 초기 N이 1일 때만 값을 정해주면 이후에는 N-1번째의 값을 이용해 N번째를 구할 수 있다. 따라서 DP로 해결할 수 있게된다.

 

 

Python3

import sys
N = int(sys.stdin.readline())
dp = [[0]*10 for i in range(N+1)]
for i in range(1, 10):
    dp[1][i] = 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]
print(sum(dp[N]) % 1000000000)

dp[i][j] : i개의 자리수 일때 뒤에 j가 올 경우 앞에 올 수 있는 수들의 가지수 합 

 

다음과 같이 채워진다...

dp[i][j]	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	0	1	2	2	2	2	2	2	2	1
3	0	2	3	4	4	4	4	4	4	2

---