9465

편집 시간: 2022년 5월 14일 오후 10:33

코드

Algorithm/9465.py at main · Junroot/Algorithm

풀이

일단, 2줄의 스티커이므로 각 열마다 하나의 스티커만 선택할 수 있다는 것을 알 수 있었다. 그래서 처음에는 각 열마다 지그재그로 스티커를 선택한 두 가지 경우중 최대값이 정답이라고 생각했다. 하지만, 아래와 같이 한 열을 포기하고 선택하는 경우가 더 최대인 경우가 있었다.

그래서 dp로 문제를 접근했다.

f(x, y): 0번열부터 x열까지에서 x열 y행을 마지막으로 선택하는 경우의 최대값

f(x, y) = max( f(x-1, 1-y), f(x-2, 1-y) ) + sticker(x, y)