Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- graph
- DP
- dfs
- 정수론
- Math
- BFS
- 따라하며 배우는 C언어
- Python
- udemy
- BASIC
- programmers
- 따라하면서 배우는 C언어
- BOJ
- greedy
- 생활코딩
- 종만북
- Cleancode
- String
- 백준
- C언어
- C
- sorting
- JavaScript
- php
- server
- Algorithm
- 인프런
- 따배씨
- Algospot
- web
Archives
- Today
- Total
몽상실현개발주의
[BOJ] 10844 / 쉬운 단계 수 / Python 본문
[BOJ] 10844 / 쉬운 단계 수 / Python
풀이
처음 시도는 경우의 수가 정해져 있다고 생각하여, N 으로 구하는 점화식을 세우려고 하였다.
하지만 매우 복잡한 점화식이 세워졌고, 그 답은 보기 좋게 오답이 나왔다.
문제를 풀기 위한 생각의 방향은,
숫자의 자리수가 늘어날때 조건이 있고, 그 조건으로 인해 경우가 좁혀져 패턴이 발생한다는 것이다.
N = 1 -> 1 2 3 4 5 6 7 8 9
N = 2 -> 10 12
21 23
32 34
43 45
54 56
65 67
76 78
87 89
98
N = 3 -> 101 121 123
210 212 232 234
321 323 343 345
432 434 454 456
543 545 565 567
654 656 676 678
765 767 787 789
876 878 898
987 989
위에서 나열한 N=3 까지의 모든 경우를 패턴이 보이도록 정리해 보았다.
N = 1 -> 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1
N = 2 -> 10 21 12 23 34 45 56 67 78 89
32 43 54 65 76 87 98
1 1 2 2 2 2 2 2 2 1
N = 3 -> 210 101 212 123 234 345 456 567 678 789
121 232 323 434 545 656 767 878 989
321 432 343 454 565 676 787 898
543 654 765 876 987
1 3 3 4 4 4 4 4 3 2
끝자리 수를 기준으로 정리를 하였더니, 만들수 있는 경우의 수의 규칙이 눈이 보였다.
끝자리 수 0 1 2 3 4 5 6 7 8 9
-----------------------------------
N = 1 -> 0 1 1 1 1 1 1 1 1 1
N = 2 -> 1 1 2 2 2 2 2 2 2 1
N = 3 -> 1 3 3 4 4 4 4 4 3 2
어떤 숫자를 1의 자리로 만들수 있는 '계단수' 의 개수는, 그 어떤 수의 + 1 과 -1 한 숫자로 만들수 있는 이전 자리수 개수의 합.
dp 를 이차 배열로 만들었을 경우, 대각선 위의 수들의 합 : dp[N][i] = dp[N][i-1] + dp[N][i+1]
위의 이차원 배열과 dp 를 이용한 풀이는 다음과 같다.
N = int(input())
dp = [[0 for _ in range(10)] for _ 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)
※ 문제를 해결하기 위한 자료구조의 다양한 형태에 대해 열린생각이 필요하다는 것을 느꼇다. 매몰되지 말자!
참고 블로그
https://pacific-ocean.tistory.com/151
'Algorithm PS > BOJ' 카테고리의 다른 글
[BOJ] 2193 / 이친수 / Python (0) | 2021.05.11 |
---|---|
[BOJ] 11058 / 오르막 수 / Python (0) | 2021.05.11 |
[BOJ] 9095 / 1, 2, 3 더하기 / Python (0) | 2021.05.10 |
[BOJ] 11727 / 2×n 타일링2 / Python (0) | 2021.05.10 |
[BOJ] 11726 / 2×n 타일링 / Python (0) | 2021.05.09 |
Comments