94651 [BOJ] 9465번: 스티커 9465번: 스티커 해법 처음 내가 접근했던 방법은 그냥 무식하게 대각선으로만 생각하고 풀었다. 그래서 당연히 틀렸고 친구와 다른 분들의 도움을 받아서 이 문제를 풀게 됐다. 우선 이 문제는 DP이고 DP식은 dp[i][j]: i열,j행까지의 스티커의 최대값이다. 하나를 선택하면 상하좌우를 선택하지 못하기 때문에 기본적으로 이동은 대각선으로만 가능하다. 그래서 DP식을 대각선쪽만 생각해서 짜면 절대 안된다. 이렇게 한다면 250이 최대가 되어서 정답인 260이 아니게 된다. 즉 한 칸을 건너뛰어야 한다. 그러면 두 칸을 건너뛰는 것은 어떨까..? 결론부터 말하자면 손해다. 두 칸을 뛰게 되면 한 칸씩 대각선 건너는 것과 같은 지점을 가지만 거치는 것은 더 적으므로 항상 손해일 수 밖에 없다. 그래서 점화.. 2018. 8. 30. 이전 1 다음