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].


이런 식으로 점화식을 세우고 문제를 풀어서 맞았는데, 이게 제대로 된 사고 과정을 거친 건지, 운이 좋아서 맞춘건지 감이 오지 않습니다.

최대한 현재 문제와 더 작은 문제로 나눈다는 개념을 생각해서, 현재 선택할 수 있는 것에 집중하였습니다.


도움을 주신다면, 정말 감사하겠습니다..!

jun83   1년 전

문제를 맞았다면 옳은 풀이입니다. 저 같은 경우는 dp[i][j] = i,j칸에 스티커를 붙였을 때 최댓값이라고 가정해서 풀었습니다. 이렇게 하면 좋았던 점은 i,j칸에서는 무조건 스티커를 붙여야 하기 때문에 조금 더 간소화된다는 장점이 있습니다. 참고만 하시면 좋을 것 같습니다.

rud15dns   1년 전

답변 감사드립니다!

만약 dp[i][j]를 i,j칸에 스티커를 붙였을 때의 최댓값이라고 가정하면은, 안 붙였을 경우는 아래(또는 위)를 붙였을 경우로 생각해서 계산하는 것이 맞는지 궁금합니다!

양옆을 고려하지 않아도 괜찮은지 궁금합니다. 괜찮다고 생각했는데, 어떻게 구현해야 할지 몰라서 구현을 못했었습니다...

jun83   1년 전

모든 스티커의 점수가 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에 대한 정당성을 도출하는지 덕분에 명확히 알 수 있었습니다.

답변 정말 감사합니다!!!

댓글을 작성하려면 로그인해야 합니다.