백준 10844 - 쉬운 계단 수
https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
이 문제는 N을 입력 받아 길이가 N인 계단 수의 갯수를 구하는 문제이다.
문제는 이해가 갔는데 도저히 코드로 옮길 수 없어서 결국엔 또 구글링ㅋ,,
코드는 의외로 굉장히 간단했다.
[백준] 10844 쉬운 계단 수 - Python
백준 10884 쉬운 계단 수45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는
velog.io
위 포스팅에 원리에 대한 자세한 설명이 있으니 참고하면 좋을 것 같다.
풀이 코드)
n = int(input())
dp = [[0] * 10 for i in range(n)]
dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(1, n):
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]
print(sum(dp[n-1])%1000000000)
이제 풀이 코드에 대한 리뷰를 해보도록 하자.
일단, 위 알고리즘을 짜기 위해서는 계단 수를 만들어내는 것에 대한 이해가 필요하다.
계단 수란, 인접한 모든 자리의 차이가 1이 나는 수를 말한다.
첫 번째로, 길이가 0인 계단수를 생각해보자
길이가 0이므로 어떠한 수도 올 수 없다 ==> 0개
두 번째로, 길이가 1인 계단수를 생각해보자
1, 2, 3, ..., 8, 9 => 총 9개가 존재한다.
0이 포함되지 않은 이유는 0으로 시작하는 수는 계단 수가 아니기 때문이다.
세 번째로, 길이가 2인 계단 수를 생각해보자
10, 12, 21, 23, 32, 43, 34, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 ==> 17개
계단수를 보면, 규칙이 좀 보인다.
일단, 문제 조건 상에 0으로 시작하는 수는 계단 수가 아니라고 했으므로 시작하는 숫자말고 끝나는 숫자를 기준으로 생각해보도록 하자.
0으로 끝나는 경우 => 0과 인접한 숫자인 1만 앞에 올 수 있다.
1로 끝나는 경우 => 1과 1차이가 나는 수인 0, 2가 1 앞에 올 수 있다.
(단, 0으로 시작하는 수는 계단수가 아니므로 결론적으로 2만 1 앞에 올 수 있다.)
2로 끝나는 경우 => 2와 1차이가 나는 수인 1, 3이 2 앞에 올 수 있다. => 2개
3로 끝나는 경우 => 3와 1차이가 나는 수인 2, 4가 3 앞에 올 수 있다. => 2개
4로 끝나는 경우 => 4와 1차이가 나는 수인 3, 5가 4 앞에 올 수 있다. => 2개
5로 끝나는 경우 => 5와 1차이가 나는 수인 4, 6이 5 앞에 올 수 있다. => 2개
6로 끝나는 경우 => 6와 1차이가 나는 수인 5, 7이 6 앞에 올 수 있다. => 2개
7로 끝나는 경우 => 7와 1차이가 나는 수인 6, 8이 7 앞에 올 수 있다. => 2개
8로 끝나는 경우 => 8와 1차이가 나는 수인 7, 9가 8 앞에 올 수 있다. => 2개
9로 끝나는 경우 => 9와 1차이가 나는 수인 8만 9 앞에 올 수 있다.
위를 알고리즘화 해보자면, 0과 9를 제외한 1~8인 수들은 모두 인접한 수 2개씩을 갖고,
0과 9는 각각 1과 8만을 인접한 수로 갖는다.
따라서, 조건문으로 경우의 수를 나누어 알고리즘화 해야한다.
계단 수는 인접한 각 자리수의 차이가 1인 수이기 때문에, 기차줄처럼 한 줄로 쭉- 연결되어 있다.
dp[i][j] = 길이가 i이고 맨 끝이 k일 때의 계단 수의 갯수 라고 하면,
k앞에는 k와 1차이가 나는 수인 k-1, k+1이 올 수 있으므로 길이가 i-1일 때 끝이 k-1인 계단수의 갯수 + 길이가 i-1일 때 끝이 k+1인 계단수의 갯수로 구할 수 있다.
이걸 점화식으로 표현해보면 다음과 같다.
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
위의 점화식은 인접한 수가 2개가 있을 경우의 점화식이므로, 인접한 수가 1개인 0과 9는 조건문으로 따로 빼서 각각 1과 8일 때의 계단 수만 저장하면 된다.