문제를 맞았다면 옳은 풀이입니다. 저 같은 경우는 dp[i][j] = i,j칸에 스티커를 붙였을 때 최댓값이라고 가정해서 풀었습니다. 이렇게 하면 좋았던 점은 i,j칸에서는 무조건 스티커를 붙여야 하기 때문에 조금 더 간소화된다는 장점이 있습니다. 참고만 하시면 좋을 것 같습니다.
9465번 - 스티커
모든 스티커의 점수가 0 또는 양의 정수이기에 어떻게든 스티커를 붙이는 것이 최선임을 직관적으로 파악할 수 있습니다. 하지만 예제 입력에서 첫 번째 테스트 케이스는 꼭 각 열 마다 스티커를 붙이는 것이 최적해가 아님을 보이고 있습니다. (문제의 난이도를 낮춘다고도 할 수 있겠네요) 따라서 dp[i][j] = max(dp[i-1][j-2],dp[i-1][j-1]) + i,j칸에서의 스티커의 점수로 생각할 수 있습니다.
1) 2칸 보다 이전 칸에서 현재 칸으로 오는 경우는 생각하지 않아도 괜찮습니다. 왜냐하면 현재 칸에 도달하기 전에 하나 이상의 다른 스티커를 포함하는 것이 최적해임이 자명하기 때문입니다.
2) 그럼 정답은 max(dp)이냐고 생각하실 수 있는데 아닙니다. 1)에 따라서 한 칸 건너뛰고 현재 스티커를 선택하는 경우가 존재하지만 마지막 칸은 건너뛰는 것 보다 한 장이라도 스티커를 붙이는 것이 최적해임이 자명합니다.
댓글을 작성하려면 로그인해야 합니다.
rud15dns 1년 전
해당 문제를 풀 때, DP인 것을 알고 나서, 점화식을 세워서 풀었습니다.
무조건 정답이라는 확신은 없었으나, 다음과 같은 사고의 과정을 거쳐서 풀었습니다.
1. 마지막 정답은 max(dp[1][n-1], dp[0][n-1])이다.
2. 이 때, dp[i][j]의 값은 해당 자리에서의 점수의 최댓값이다.
3. dp[i][j]에서 가능한 경우는 다음과 같다.
1) sticker[i][j]를 선택한 경우
2) sticker[i][j]를 선택하지 않은 경우
1)의 경우에는 가능한 경우가 dp[(i + 1) % 2][j-1] 뿐이므로, sticker[i][j] + dp[(i + 1) %2][j-1].
2)의 경우에는 아래와 왼쪽의 경우가 있지만, 아래의 경우를 고려하면, max에서 중복 계산이 될 것이므로, 왼쪽 스티커를 떼어서 현재 자리 스티커를 떼지 못하는 경우만 계산한다. 따라서, dp[i][j-1].
이런 식으로 점화식을 세우고 문제를 풀어서 맞았는데, 이게 제대로 된 사고 과정을 거친 건지, 운이 좋아서 맞춘건지 감이 오지 않습니다.
최대한 현재 문제와 더 작은 문제로 나눈다는 개념을 생각해서, 현재 선택할 수 있는 것에 집중하였습니다.
도움을 주신다면, 정말 감사하겠습니다..!