동적계획법. [9465]

[1. 문제 설명]

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

---

[2. 풀이 접근]

완전 탐색 접근..

동작방식

• 이차원 배열의 좌상단 -> 우하단으로 이동하면서, 선택 여부에 따라 재귀를 호출한다.
• 현재 위치를 선택하지 않는 경우
• 현재 위치를 선택하는 경우
  => 상,하,좌,우로 인접한 위치를 선택하지 못하게 한다.
  => 재귀 호출 한다.
  => 상,하,좌,우로 인접한 위치를 다시 선택 할 수 있게 업데이트 한다.

위와 같은 동작방식에서 메모이제이션을 적용하기는 어렵다.

here 위치에서 앞으로 선택 대상은 색칠된 위치들이다.

그러나 이 위치들은 here 보다 앞선 1,2,3, 선택 여부에 따라 고려 대상이 될 수도 있고, 안될 수도 있다.

 좌상단 -> 우하단 이동 방식으로는 최적 부분 구조를 성립할 수가 없다.

 

문제의 행 개수가 2 라는 점은 풀이 접근에 대한 힌트가 되며, 아래와 같이 접근 하는 방법을 생각해볼 수 있다.

열 단위로 접근하는 것이며, 이때 다음 열의 선택가지 수는 3가지가 될 수 있다.

이 경우에는 최적부분구조를 성립 할 수 있게 된다.

바로 이전 열의 선택 유형과 현재 열을 index 로 하는 캐시를 선언하여 메모이제이션을 적용 할 수 있다.

 

참고

• https://www.acmicpc.net/board/view/2670
•  

---

반복적 동적계획법 접근

---

[3. 코드]