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 |
Tags
- likelionlikelion
- ux·ui디자인
- 프로젝트
- Plotly
- folium
- 멋쟁이사자처럼멋쟁이사자처럼
- 멋쟁이사자처럼
- seaborn
- Python
- 그리디
- 마이온컴퍼니
- 인턴10
- intern10
- Join
- DFS
- 멋재이사자처럼
- 알고리즘
- TiL
- parklab
- BFS
- 마이온
- DP
- 멋사
- GIS
- 시각화
- 온보딩
- 파이썬
- pyhton
- SQL
- likelion
Archives
- Today
- Total
지금은마라톤중
[백준] 10844번 쉬운 계단 수 본문
DP 문제가 익숙해질 때까지 난이도를 올려가면 문제를 풀어보려고 합니다.
해당 문제는 규칙성을 찾았다고 생각했는데 올바른 접근법이 아니여서 시간이 걸렸습니다.
시도
- 안 되는 경우의 수를 찾기
- 전체 경우의 수 - 안되는 경우의 수
→ 안 되는 경우의 수가 1,2,3,6,10..... 나름의 규칙성을 가졌다고 생각해서 접근법을 가졌다고 생각했으나 틀렸다.
올바른 접근법
- 각 자리에 대한 경우를 쪼개서 생각
- 자리수가 늘어날때마다 각 숫자의 경우의 수를 생각하여 합하여 값 산출
- 일반적 경우 : 2~8은 다음 자리에 올 수 있는 경우가 2가지(이전 자리의 단계수의 경우의 수)
- 특수한 경우 : 0,9는 연속된 숫자가 1개임으로 각각 1가지 경우만 존재
- dp를 2차원 배열로 만든다( n자리수, n 자리에 올 수 있는 경우의 수)
-> 자리수가 늘어날 때마다 각 숫자에 올 수 있는 이전 자리의 경우의 수를 더해준다
ex) ?3 →23,43의 각 경우의 수를 더해준다 , ?9 → 89의 경우의 수만 해당
n = int(input())
dp = [[ 0 for _ in range(10)] for _ in range(n)]
dp[0] = [0] + [1]*9
for i in range(1,n):
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-1])%1000000000)
'STUDY > Python 알고리즘' 카테고리의 다른 글
[백준] 11726번 2xn 타일링 (0) | 2024.05.15 |
---|---|
[백준] 1699번 제곱수의 합 (0) | 2024.05.09 |
[백준] 2193번 이친수 (0) | 2024.05.01 |
[백준]1463번 1로 만들기 (3) | 2024.05.01 |
[백준] 2579번 계단오르기 (0) | 2024.04.09 |
Comments