✅ DP

문제

링크

1. 문제 접근 및 해결 로직

문제에서 $P(1)$ ~ $P(10)$ 까지의 답을 알려줬으므로 규칙만 찾으면 된다.
1, 1, 1, 2, 2, 3, 4, 5, 7, 9

앞에 3개는 모두 1로 똑같으므로 넘어가고 2부터 보자

• N=4, 2 = 1+1 이니까 앞에 3개에서 2개 값을 뽑아서 더한 것이라는 걸 알 수 있다.
• N=5, 그다음은 또 2이다. 특이하다.. 일단 이전 2와 똑같이 앞에 3개에서 2개 값을 뽑아서 더한 것이라는 것만 생각하고 넘어가자
• N=6, 3 = 2+1이다.
• N=7, 4 = 2+2이다.

이제 규칙이 보인다. N의 값 = N-2의 값 + N-3의 값

• 정의
  $P(N)$ : 나선에 있는 n번째 정삼각형의 변의 길이
• 구하는 답
  $P(N)$
• 초기값
  $P(0)=1$
  $P(1)=1$
  $P(2)=1$
• 점화식
  $P(N)=P(N-2)+P(N-3)$

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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