[BOJ] 9465번 스티커 (파이썬)

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제 입력 1 복사

2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80

예제 출력 1 복사

260
290

 

 

 

---

 

입출력을 좀 풀다가 이제서야 DP로 넘어온 코린이....

지금까지 겪어본 DP는 피보나치 유형, 계단수 유형 뿐!!!

경험에 빗대어 해결책을 생각하다 보니 새로운 과정을 생각해내기 굉장히 어렵습니당.

 

첫 도전

일단 문제를 보자마자 그리디가 아닌 건 파악할 수 있었습니당.

생각회로 : 

포인트들을 담는 이차원 리스트 하나, 점수들을 담을 일차원 리스트 하나를 선언

↓

가장큰 point[i][j]를 선택 

↓

주변 point들(ex. [i-1][j], [i+1][j] 등등...)을 0으로 교체

↓

그리고 남은 point들의 합이 가장 클 때(즉, 선택한 포인트도 최대, 남은 포인트 합도 최대일 때) 해당 point를 d[i]에 입력

 

이걸 생각해낸 후 와 나도 드디어 머리가 좀 돌아가나보다 뿌듯...

하지만 봉착한 문제, 이차원 배열에서의 최대값을 어떻게 찾지? -> map함수 사용

인근 포인트들을 0으로 바꿔줘야하는데 이차원 배열 최댓값 인덱스는 어떻게 찾지? -> 반복문 사용...?

멘붕... 머야머야

지금 생각해보면 저 방법은 dp도 아닐 뿐더러 허무맹랑한 소리였다...ㅠㅠ

 

재도전

to be continued.....

갈 수 있는 방향이 정해져 있었던 것............