✅ DP

문제

링크

1. 문제 접근 및 해결 로직

크게 두가지 경우가 있다.
1. n-1 과 n을 하나의 단어로 보는 경우
2. n-1 과 n을 개별 단어로 보는 경우

1번의 경우 n-1 과 n으로 만든 수가 10~26 사이어야 한다.
2번의 경우 n은 1~9 사이어야 한다. (0은 개별로 볼 수 없음)

$dp[n]$ : n번째 숫자까지 읽을 수 있는 단어의 갯수라고 하자.
1번의 경우라면 n-1과 n은 한몸이므로 n-1에서의 단어의 갯수는 세주지 않아도 된다.

• 정의
• 구하는 답
• 초기값
• 점화식

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항