동적계획법. [9461]

[1. 문제 설명]

https://www.acmicpc.net/problem/9461

---

[2. 풀이 접근]

1. 완전 탐색에서 시작한다.
2. 중복되는 부분문제를 파악한다.
3. 메모이제이션을 적용한다.

위 그림에서 가운데 길이가 1인 정삼각형을 P(1)

그 왼쪽 정삼각형을 P(2)

P(2) 의 위쪽 정삼각형을 P(3) 로 정의하고, 나선 방향으로 식을 정리하면 아래와 같게 된다.

 

p(1)  = 1
p(2)  = 1
p(3)  = 1
p(4)  = p(3)+p(1)  = 2
p(5)  = p(4)       = 2
p(6)  = p(5)+p(1)  = 3
p(7)  = p(6)+p(1)  = 4 # p(1)==p(2)
p(8)  = p(7)+p(3)  = 5
p(9)  = p(8)+p(4)  = 7
p(10) = p(9)+p(5)  = 9
p(11) = p(10)+p(6) = 12
p(12) = p(11)+p(7) = 16
p(13) = p(12)+p(8) = 21
p(14) = p(13)+p(9) = 30

 

따라서 점화식은 아래와 같다.

p(n) = p(n-1)+p(n-5) (n > 5)

 

이제, 메모이제이션을 적용 할 수 있다.

 

cf)

golang 으로 작성해서 까먹고 있었는데, 자료형 범위 역시 신경써야 한다.

---

[3. 코드]