728x90
반응형
https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
예시에서 입력이 1이면 즉, N이 1일 경우는 출력이 9이다. 다른 예시를 살펴보면 입력이 2이면 출력이 17이다.
길이가 2인 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98이다. 이 개수를 1,000,000,000으로 나누면 17이 됩니다.
우선 숫자를 가지고 자릿수를 늘려가면서 가능한 계단 수를 확인해 보겠습니다.
위의 그림을 표로 정리해보면 아래와 같습니다.
| 숫자|단계 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 1 | 1 | 2 | 3 | 6 | ... |
| 1 | 1 | 2 | 3 | 6 | 10 | ... |
| 2 | 1 | 2 | 4 | 7 | 14 | ... |
| 3 | 1 | 2 | 4 | 8 | 15 | ... |
| 4 | 1 | 2 | 4 | 8 | 16 | ... |
| 5 | 1 | 2 | 4 | 8 | 16 | ... |
| 6 | 1 | 2 | 4 | 8 | 15 | ... |
| 7 | 1 | 2 | 4 | 7 | 14 | ... |
| 8 | 1 | 2 | 3 | 6 | 10 | ... |
| 9 | 1 | 1 | 2 | 3 | 6 | ... |
아래와 같은 규칙을 볼 수 있습니다.
0과 9를 제외한 수는 이전 단계에서 [자신보다 작은 수 + 자신보다 큰 수]의 값인 것을 알 수 있습니다.
0과 9는 이전 단계의 1과 8단계의 값인 것을 알 수 있습니다.
코드로 작성하면 다음과 같습니다.
|
for i in range(1, N+1):
for j in range(10):
if 1 <= j <= 8:
stair_nums[i][j] = stair_nums[i - 1][j - 1] + stair_nums[i - 1][j + 1]
elif j == 0:
stair_nums[i][j] = stair_nums[i - 1][j + 1]
elif j == 9:
stair_nums[i][j] = stair_nums[i - 1][j - 11]
|
여기서 주의할 점은 N이 1일 때는 모든 값이 1이어야 합니다. 이 값을 위해서 stair_nums의 초기값을 모두 1로 준 뒤 i for문을 2부터 실행시키면 됩니다. 그리고 출력은 1,000,000,000으로 나눈 나머지 값을 출력해야 합니다.
여기서 101개의 값을 생성한 이유는 N의 입력값이 100 이하이기 때문입니다.
전체 코드
|
# 백준 10844 / 쉬운 계단 수
if __name__=='__main__':
N = int(input())
stair_nums = [[1 for _ in range(10)] for _ in range(101)]
for i in range(2, N+1):
for j in range(10):
if 1 <= j <= 8:
stair_nums[i][j] = stair_nums[i - 1][j - 1] + stair_nums[i - 1][j + 1]
elif j == 0:
stair_nums[i][j] = stair_nums[i - 1][j + 1]
elif j == 9:
stair_nums[i][j] = stair_nums[i - 1][j - 11]
print(sum(stair_nums[N][1:10]) % 1000000000)
|
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [python/11053]가장 긴 증가하는 부분 수열 (0) | 2020.04.29 |
|---|---|
| [python/2156]포도주 시식 (0) | 2020.04.27 |
| [python/1463]1로 만들기 (0) | 2020.04.21 |
| [python/2579]계단 오르기 (0) | 2020.04.18 |
| [python/1932]정수 삼각형 (0) | 2020.04.16 |