[백준 알고리즘] 9465번 스티커

문제

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

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

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

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

입력과 출력

입력은 테스트케이스 개수가 주어지고 그다음은 n값, 그 이후 n개의 값이 들어오며 그 위치에 해당하는 스티커의 점수

출력은 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최대값

풀이

혼자 시작을 못하겠어서 힌트를 살짝봤는데.. 2개의 변수를 이용해서 점화식을 세운다

하나의 스티커에 대해서 그 스티커를 뗄수있는지 그 앞의 스티커는 어떻게 했는지를 나타내는 함수를 만든다

sticker(i, status) 에서 i번째부터 스티커를 떼기 시작해서 얻을 수 있는 최대값을 구한다  i는 이 함수에서 볼 몇번째 스티커인지를 뜻한다 

status는 앞의 스티커에 대한 뜻을 나타내는데 0이라면 바로 왼쪽 열에서 스티커를 떼지않았다는 뜻이고, 1이라면 위쪽 스티커를 2라면 아래쪽 스티커를 뗐다는 뜻이다

sticker(0,0)에서 시작하게되면 

1. 위쪽 스티커를 떼게 되었을 때 sticker(1,1)+위쪽스티커의 점수

2. 아래쪽 스티커를 떼게 되었을 때 sticker(1,2)+아래쪽스티커의 점수

3. 아무 스티커도 떼지 않았을 때 sticker(1,0)

이 중 가장 큰 값을 답으로 가진다

sticker에서 위의 3가지를 이용 + status를 통해서 조건절을 만든다

* 문제에서  (1 ≤ n ≤ 100,000) 라고 조건을 줬는데 최대크기를 1000으로 둬서 계속 런타임에러가 났다 

코드

int sticker(int c, int status)

{

int result;

if(c == n) return 0;

if(dp[c][status]!= -1) return dp[c][status]; //이미 값이 계산됐으면

result = sticker(c+1, 0);

if(status != 1)//옆스티커 위의 스티커를 뗌

result = max(sticker(c+1,1)+score[1][c], result);

if(status != 2)

result = max(sticker(c+1,2)+score[0][c], result);

dp[c][status] = result;

return result;

}