문제출처 : 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

+ Recent posts