allgoodlife   4달 전

이번 문제의 점화식은 다음과 같이 세웠습니다.

문제에 나와있는 Test Case는 잘 구해지는데 어느 부분이 틀렸는지 잘 모르겠습니다. 반례 혹은 점화식이 잘못된 것을 지적해주시면 감사하겠습니다.

n=1,2 일때까지는 구해줍니다.

n>3 부터는 아래 그림과 같은 점화식으로 문제를 해결하려고 합니다.

간단히 그림을 설명드리자면, n번째 dp[i][j]는 dp[0][j], dp[1][j]로 나누어 구합니다.(파란색, 빨간색)

1) dp[0][j] -> j번째 열의 0행 스티커를 떼어낼 때, 가장 높은 점수로 떼어내는 방법

2) dp[1][j]-> j번째 열의 1행 스티커를 떼어낼 때, 가장 높은 점수로 떼어내는 방법입니다.

최종 결과는 1과 2의 최댓값으로 구합니다.


좀 더 세부적으로 설명드리면,

1)은 아래 그림의 1,2번 케이스로 나누어지므로 두 경우의 max값

2)는 아래 그림의 3,4번 케이스로 나누어지므로 두 경우의 max값으로 구합니다.

그 다음 최종 결과는 1과 2의 최댓값으로 구합니다.

79593cd596ef0bcefc79a8f10bcad82d.png



반례 혹은 점화식의 잘못된 부분을 알려주시면 감사하겠습니다.

f52985   4달 전

1

4

100 1 1 100

1 1 100 1


정답 : 300

출력 : 202


DP[][j-2]를 사용하지 않는 경우가 최선일 수도 있습니다.


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