문제출처 : https://www.acmicpc.net/problem/9465
1. 문제요약
- 2xn 스티커 배열
- 한장을 떼면 변을 공유하는 좌, 우, 상 또는 하 의 스티커는 못쓰게 됨
- 스티커당 점수가 있는데 뗀 스티커의 점수의 최대 합은?
- 1 <= n <= 100,000
2. 접근방법
- 브루트 포스로 접근하면, 2^100000
못품
- dp로 접근하면,
: 회색 스티커를 뗀다면, 노란색 스티커 또는 초록색 스티커를 뗀 경우 최대가 된다
: 각각 회색이 윗칸을 뗀경우, 아랫칸을 뗀 경우로 구분
3. 시간복잡도
- n
4. 회고
소스코드
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
'먹고살려면 > boj' 카테고리의 다른 글
BOJ 11053 가장 긴 증가하는 부분 수열(LIS) (0) | 2018.01.20 |
---|---|
BOJ 2156 포도주 시식 (0) | 2018.01.18 |
BOJ 2193 이친수 (0) | 2018.01.16 |
BOJ 11057 오르막 수 (0) | 2018.01.16 |
BOJ 10844 쉬운 계단 수 (1) | 2018.01.16 |