백준: #10844.쉬운 계단수 / DP / Silver1

문제 링크 : https://www.acmicpc.net/problem/10844

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

문제 요약

• 계단수의 인접한 모든 자리는 차이가 1
• 길이가 N인 계단수의 총 개수 구하기 = 목표
• 0으로 시작하는 수는 계단수가 아니다
• 출력은 정답을 1,000,0000으로 나눈 나머지

입력 : 1≤N≤100인 자연수

풀이 유형 : DP

<aside> ✅

모든 가능한 경우 을 고려하여 조건에 맞는 수를 만들되 , 중복 계산 피하라

DP

(1) 큰문제 → 작은 문제로 분해 가능 : 길이 N인 계단수 = 길이 N-1 계단수 + 숫자 1개 붙이기

(2) 작은 문제가 중복 등장 : dp[5][2] = dp[4][1] +dp[4][1]

(3) 이전 결과 재사용 가능 : 이전 n-1 길이인 경우의 수로 부터 길이 n인 경우의 수 간으

</aside>

Q. “모든 경우를 탐색” 해야하는가 → 완전 탐색 , DFS , DP 중 하나

Q2. 중복되는 계산이 발생하는가 ? → DP 가능성 높음

길이 5 , 마지막 숫자 2 인 계단수는 여러 경로로 도달함

Q3. 작은 문제로 큰 문제를 만들 수 있늕

길이 5는 길이 4에 숫자 하나 붙여서 만들 수 있음

Q4. 최대수 or 개수 → DP 문제 가능성 높음