스티커 (실버 1) [Class 4]

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

9465번: 스티커

1 초

256 MB

73396

34595

24514

46.854%

문제

상근이의 여동생 상냥이는 문방구에서 스티커 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

문제 해결

문제를 보자마자 일단은 바로 그리디하게 접근했다. 결국은 현재 스티커 중 최댓값을 가져오고 상하좌우로 날리고 다시 최댓값을 가져오고... 이런 방식으로 생각했는데 정렬 시간복잡도는 커버가 되어도 N만큼 돌면서 최댓값 상하좌우의 좌표를 찾고 제거하는데 N^2만큼의 시간복잡도가 걸릴것이라 판단하고 DP로 생각을 틀었다.

 

우선 직관적으로 생각하기 편하게 2차원 DP테이블을 만들어서 갱신했다. 로직 자체는 간단하다.

• 선택할 수 있는 스티커는 위 또는 아래밖에 없다.
• 아래를 선택하기 위해서는 이전 값에서 위를 선택해야한다.
• 위를 선택하기 위해서는 이전 값에서 아래를 선택해야한다.

 

당연하게 스티커를 위 또는 아래 선택하는 경우의 수 2가지라고 간단하게 생각하고 로직을 짜고 예제를 확인하는데 스티커를 선택하지 않아야 최댓값이 갱신되는 경우가 있다는 걸 확인했다. 그래서 다시 로직을 고민한 결과 아래와 같은 점화식을 세울 수 있었다.

 

dp[UP][N] = MAX( dp[DOWN][N-1], dp[UP][N-2], dp[DOWN][N-2]) + 현재스티커[UP][N]

 

아래는 위에서 UP => DOWN으로 바꾼것이므로 패스하고 해당 로직을 하나씩 따라가면 다음과 같다.

 

1. 먼저 N=2까지는 스티커가 음수가 아닌 이상 무조건 더해주는게 이득이므로 초기 테이블은 다음과 같이 셋팅했다.

dp[UP][1] = sticker[UP][0]
dp[DOWN][1] = sticker[DOWN][0]
    
if N <= 1:
	print(max(sticker[UP][0], sticker[DOWN][0]))
	continue
    
dp[UP][2] = dp[DOWN][1] + sticker[UP][1]
dp[DOWN][2] = dp[UP][1] + sticker[DOWN][1]

 

스티커 테이블

	1	2	3	4	5
UP	50	10	100	20	40
DOWN	30	50	70	10	60

 

DP

	1	2	3	4	5
UP	50	40
DOWN	30	100

 

2. 이제 위에서 세웠던 점화식에 따라 N이 3~5까지 테이블이 갱신되는것은 다음과 같다.

dp[UP][N] = MAX( dp[DOWN][N-1], dp[UP][N-2], dp[DOWN][N-2]) + 현재스티커[UP][N]

 

DP (N = 3)

3번째 UP

• 1칸 이전의 DOWN  = 100
• 2칸 이전의 UP = 50
• 2칸 이전의 DOWN = 30

위 3개의 값 중 최댓값과 자신의 스티커 값을 더해주면 된다. 현재는 100이 최댓값이므로 100(최댓값) + 100(자신의 스티커)

	1	2	3	4	5
UP	50	40	200
DOWN	30	100

위와 같은 방식으로 DOWN도 해주면 최댓값 50 + 스티커 70으로 120의 값이 갱신된다.

	1	2	3	4	5
UP	50	40	200
DOWN	30	100	120

 

DP (N = 4)

4번째 UP 

• 1칸 이전의 DOWN  = 120
• 2칸 이전의 UP = 40
• 2칸 이전의 DOWN = 100

120 + 자신의 스티커값(20)

	1	2	3	4	5
UP	50	40	200	140
DOWN	30	100	120

4번째 DOWN

• 1칸 이전의 UP  = 200
• 2칸 이전의 UP = 40
• 2칸 이전의 DOWN = 100

200 + 자신의 스티커값(10)

	1	2	3	4	5
UP	50	40	200	140
DOWN	30	100	120	210

 

DP (N = 5)

5번째 UP 

• 1칸 이전의 DOWN  = 210
• 2칸 이전의 UP = 200
• 2칸 이전의 DOWN = 120

210 + 자신의 스티커값(40)

 

	1	2	3	4	5
UP	50	40	200	140	250
DOWN	30	100	120	210

 

5번째 DOWN

• 1칸 이전의 UP  = 140
• 2칸 이전의 UP = 200
• 2칸 이전의 DOWN = 120

200 + 자신의 스티커값(60)

	1	2	3	4	5
UP	50	40	200	140	250
DOWN	30	100	120	210	260

 

위 처럼 테이블을 갱신하고 나면 이제 UP과 DOWN 중 최댓값을 출력해주기만 하면 된다!

 

테이블 갱신 코드

for i in range(3, N+1):
	dp[UP][i] = max(dp[DOWN][i-1], dp[UP][i-2], dp[DOWN][i-2]) + sticker[UP][i-1]
	dp[DOWN][i] = max(dp[UP][i-1], dp[UP][i-2], dp[DOWN][i-2]) + sticker[DOWN][i-1]
        
print(max(dp[UP][N], dp[DOWN][N]))