BOJ 9465 - 스티커

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

예전 풀이: http://joonas-yoon.blogspot.com/2014/08/9465.html

풀이

한 스티커(칸)를 선택하면 인접한 칸은 선택할 수 없게 된다.

그럼 대각선만 남게 되는데, 그 대각선 칸도 위 선택을 반복하게 된다.

A B C D

E F G H

만약 위와 같이 있다고 생각해보자. A를 고른다면 C, D, F, G, H 중에 골라야한다. E를 고른다면 B, C, D, G, H 중에 골라야한다.

바로 다음 칸(열)에만 영향이 있고, 그 이후의 C, D, G, H를 고민하는 것은 변함이 없다. 즉 어떤 i번째 열을 볼때, i+2번째 이후의 열은 영향이 없다는 뜻이다.

i번째 열에서 고민할 점은 3가지이다.

1. 고르지 않는다.

이번 열은 고르지 않는 경우가 더 높을 수 있다.

100 20 40

 70 10 60

이런 경우에는 가운데 열을 고르지 않으면 100+60 = 160점을 얻을 수 있다.

2. 위쪽 스티커를 고른다.

그럼 선택할 수 있는 것은 i+1번째에서 대각선에 있는 스티커밖에 없다.

3. 아래쪽 스티커를 고른다.

2번과 마찬가지로 대각선에 있는 스티커만 고를 수 있다.

모든 열에 대해서 각 경우를 계산하고 선택한 스티커의 점수를 누적해나간다.

코드