백준 9465번 스티커 C++

 

 

1. 문제 해결

문방구에서 스티커 2n개를 구매했다.

스티커는 2행 n열로 배치되어 나온다.

해당 스티커로 책상을 꾸미려고 하는데

스티커를 한장 떼면 해당 스티커의 상하좌우에 있는 스티커에도 영향을주어 사용할 수 없게 되어버린다.

각 스티커에는 값어치가 매겨져있어 그 값어치를 최대로 하게 끔 스티커를 떼어 책상을 꾸미려고 한다.

 

처음 dfs + 백트래킹 문제라고 생각하여 문제를 풀어보려고 하였으나 점점 산으로 가는 코드에 다른 방법이 있는것을 알았다

이 문제는 dp를 이용한 문제로 점화식을 찾아 푸는 문제이다.