[PS] 2013 Daejeon 6510 Stickers

본 문제는 스티커의 합이 최대가 되도록 뽑아야하는데, 인접한 스티커 두개는 뽑을 수 없다.

위와 같이 스티커가 있을떄, 맨 왼쪽 줄에 50을 골랐으면

밑에 30과 오른쪽의 10은 고를수 없다는 소리다.

그리고 선택을 안할수도 있다.

중요한건 선택하냐, 위에껄 선택하냐, 밑에껄 선택하냐 이 3가지 선택지다.

이를 트리구조로 표현하면

![]9http://2.bp.blogspot.com/-s2mCVIa0N8/VfrJwD4F0RI/AAAAAAAAEts/pny78-K3jOY/s640/KakaoTalk20150917_230935903.jpg)

위와 같이 선택 트리가 구현된다.

50을 고르면 그 옆에 10은 못고르므로, 아무것도 고르지않는다와, 2번째 카드를 고르는

2가지 경우가 그림에서 표현되어있다.

하지만 저런식으로 코딩을 하면 존나 느리므로

이 문제는 O(n) Dynamic Programming 으로 풀 수 있다.

원리는 존나 간단하다.

row 가 3인 배열을 만들고 col은 입력데이터의 개수 N 이다.

선택하지않음 , 1번카드선택 , 2번카드선택

으로 구분한다.

1번 카드에 대해 선택하지 않은것과 선택한것들에 대해 값을 쓴다.

그럼

[0] [50] [30] 이 될것이다.

두번쨰 배열부터는 첫번째 식이 사용된 값으로 계산한다.

아무것도 선택하지 않은 값에 대해선 모두 계산을 하고,

첫번째 카드와 두번째 카드는 각각 인접한 카드를 고를수없으므로,

고르지않는다, 대각선카드를 고른다, 두가지 경우가 나온다.

각 값에 따라 큰 값을 다음 배열에 저장하면 다음과 같다.

[0] [50] [30] [50] [40] [100]

이런식으로 모든 카드에 대해 계산을 하면 O(N)으로 DP 계산을 끝낼 수 있다.