9465

[python3] 백준 9465 풀이 ( 스티커, 다이나믹 프로그래밍, 이차원 배열 )

문제를 쓱 읽어 보면 DP의 냄새가 솔솔솔~ 난다. 딱 봐도 그리디로 풀 수 없고 완전 탐색을 진행해야만 풀 수 있는 상황이다. 그렇다면 역시 DP로 풀어야한다. DP로 풀기 위해서는 다음 단계에 영향을 미쳐야 한다. 즉, 선택한 스티커의 상하좌우에 위치한 다른 스티커를 선택할 수 없다. 우선 dp를 이차원배열이라 한다. 또한 dp에는 각 행별로 열까지의 최댓값을 가진다. 따라서 천천히 생각해보자 만약 0열의 i를 뽑을 것이라면 0열의 dp[0][i-1]을 뽑을 수 없다. 따라서 0열이 아닌 1열의 i-1까지인 dp[1][i-1]을 더할 수 있다. 그러면 식은 dp[0][i] = dp[1][i-1] 이다. 또한 한가지를 더 생각해 보아야 한다. i-1의 열의 스티커의 값이 형편 없다면 이걸 무시하고 i-..