관리 메뉴

Joonas' Note

BOJ 9465 - 스티커 본문

알고리즘/문제 풀이

BOJ 9465 - 스티커

joonas 2019. 2. 24. 00:33

링크: 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번과 마찬가지로 대각선에 있는 스티커만 고를 수 있다.


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

코드


반응형

'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 1976 - 여행 가자  (0) 2019.03.08
BOJ 1613 - 역사  (0) 2019.02.24
BOJ 9465 - 스티커  (0) 2019.02.24
BOJ 10472 - 십자뒤집기  (0) 2019.02.23
BOJ 1939 - 중량 제한  (0) 2019.02.23
BOJ 10799 - 쇠막대기  (0) 2019.02.23
0 Comments
댓글쓰기 폼