[BOJ] 9465번: Stickers

https://www.acmicpc.net/problem/9465


동적계획법으로 풀기 위해 적절한 점화식을 찾아야합니다. 각 열에 대해 변수를 2개를 두면 점화식을 쉽게 떠올릴 수 있는데, D[i][0] : 0~i-1열 전체 + i열 0행만 있다고 할 떄 최댓값, D[i][1] : 0~i-1열 전체 + i열 1행만 있다고 할 때 최댓값으로 둔다면


D[i][0] = max(sticker[i][0] + D[i - 1][1], D[i - 1][0]);


D[i][1] = max(sticker[i][1] + D[i - 1][0], D[i - 1][1]);


가 됩니다. 스티커의 값이 0이상이기 때문에 이렇게 정의할 수 있습니다. 그림을 그려서 생각해보세요.)


https://github.com/encrypted-def/BOJ/blob/master/9465.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 11727번: 2×n 타일링 2  (0) 2018.01.01
[BOJ] 11053번: 가장 긴 증가하는 부분 수열  (0) 2018.01.01
[BOJ] 1697번: 숨바꼭질  (9) 2018.01.01
[BOJ] 11726번: 2×n 타일링  (0) 2018.01.01
[BOJ] 1012번: 유기농 배추  (0) 2018.01.01
[BOJ] 2163번: 초콜릿 자르기  (0) 2018.01.01
  Comments