[백준 9465] 스티커 [Python]

백준 9465 - 문제

백준 9463 - 입/출력

---

풀이

스티커를 사용할 때 변을 공유하는 스티커는 사용할 수 없다는 조건이 있다.

따라서, 스티커를 최대한 많이 사용하고자 한다면 대각선으로 진행하며 사용할 때 가장 많은 스티커를 사용할 수 있다.

백준 9465 - 문제 (a)

총 5개의 스티커를 고를 수 있다.

 

하지만, 이러한 방식이 항상 스티커 점수들의 최댓값임을 보장하지 않는다.

문제에서 주어진 경우를 살펴보자.

백준 9465 - 문제 (b)

50 - 50 - 100 - 60 으로 총 4개의 스티커를 사용했지만, 스티커 점수들의 합은 260으로 이전에 선택한 경우보다 큰 점수를 가진다.

 

따라서, 각 스티커 영역마다 가질 수 있는 최댓값을 기록할 때 아래 그림과 같은 선택지를 고려해야 한다.

 

먼저, 단순하게 대각선으로 선택한 경우다.

주황색은 선택하지 못하는 영역,

초록색은 지금 선택한 영역,

파란색은 선택할 수 있는 이전 영역이다.

초록색 영역을 선택한 경우 파란색 영역에 기록된 최댓값을 가져오는 것이 합리적인 선택이다.

 

다음은, 위의 1번 파란색 영역보다 한 칸 뒤 영역의 값을 선택한 경우다.

주황색 영역이 1번 파란색을 선택한 경우보다 많지만, 결국 2번 파란색 영역에 기록된 최댓값이, 1번 파란색 영역에서 가질 수 있는 최댓값보다 크다면, 2번 파란색을 선택하는 게 옳을 것이다.

 

위의 과정을 아래과 같이 구현해 줬다.

---

소스코드

소스코드 보기

---

출처

9465번: 스티커