✓

태그:

CLASS 4 ESSENTIAL

떼버린 스티커의 대각선에 있는 스티커는 뗄 수 있어요!

풀이 비스무리한거 보기

2줄짜리 스티커 모음(총 2n개)이 있을 때, 하나의 스티커를 제거하면 그와 변을 공유하는 스티커가 모두 손상됩니다. 각 스티커마다 점수가 매겨져있을 때, 제거한 스티커의 점수의 합의 최대값을 구하는 문제입니다. 이 문제는 스티커의 각 열에서 제거할 스티커를 하나 고르거나 건너뛰는 경우가 있는데, 2개의 열 이상을 건너뛰는 것은 그 두 열 중 하나의 스티커를 고르는 것이 더 점수가 높으므로 안하는 것이 좋을 것 같습니다.

1열부터 k열까지 스티커를 제거하되 k열의 스티커 중 위쪽을 제거하는 경우 중 최대값인 것과 아래쪽을 제거하는 경우 중 최대값인 것을 DP로 계산해나가면 됩니다. 점화식은 아래와 같이 됩니다.

\[A_n = a_n + \max\left(b_{n-1}, a_{n-2}, b_{n-2}\right) \\ B_n = b_n + \max\left(a_{n-1}, a_{n-2}, b_{n-2}\right)\]

• A_n: n번째 열에서 위쪽 스티커를 제거하는 경우 중 점수의 합이 최대인 경우
• B_n: n번째 열에서 아래쪽 스티커를 제거하는 경우 중 점수의 합이 최대인 경우
• a_n: n번째 열의 위쪽 스티커의 점수
• b_n: n번째 열의 아래쪽 스티커의 점수

이를 구현하여 최대가 되는 값을 찾으면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-02 22:33:37

---