BOJ 5721 - 사탕 줍기 대회

문제 링크(Link)

---

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

문제 해결 (Solution)

---

 1. i번 째 행은 i+2행과는 아무 상관이 없다. i행의 열 중에서 서로 인접하지만 않으면 된다.

 2. 1의 조건을 만족시키는 DP table을 생각해보면, 행에 대한 DP와 열에 대한 DP를 따로 만들어 해결하는 게 편함.

 3. dp1[i] = i행에서의 최대값.

    dp2[j] = i행에서 열들을 선택했을 때의 가장 큰 값.

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 1. 처음엔 행과 열을 따로 생각할 수 있다는 생각을 하기 어렵다. 이런 유형이 있다는 것을 알아야한다.

 2. 행과 열의 크기가 주어지지 않으므로, 그냥 1차원 배열로 생각하고 인덱스를 잘 다뤄야한다.

참고(Reference)

---

 - 아이디어를 받은 Blog : http://sungwoo91.tistory.com/15

※ 정확하고 부드러운 태클은 언제나 환영입니다.