백준) 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

 

생각 전개 과정

스티커를 구매할 때, 2행 n열이므로 스티커를 추가로 구매할때마다 열이 늘어난다고 생각하였다.

예를들어, 아래 그림은 스티커를 2개만(n=1) 구매한 것과 4개를(n=2) 구매한 예시이다.

n=1

n=2

그렇다면

점화식을 세워서 n이 늘어날 때마다 열이 늘어난다고 생각하면 문제를 풀 수 있지않을까?

라고 다이나믹 프로그래밍으로 접근하였다.

 

n=1일때는 dp[1]을 구하고.

n=2일때는 dp[1]과 연관지어서 dp[2]를 구하는 것이다. 

(dp[i]는 2 * i개 까지의 스티커 점수의 최댓값)

 

그림으로 예를 들어보자.

2개의 스티커가 있는 아래의 그림에서는 dp[1]이 30과 50을 비교하여 50이 될 것이다. (dp[1] =50)

 

 

4개의 스티거가 있는 아래의 그림에서 dp[2]를 구하려면 dp[1]의 값을 가져온 후,

dp[1]을 위하여 찢어진 그림을 제외하고 남은 2열의 값을 가져오면 될 것이다.

 

 

 

 그림으로 그리면 이렇게 될 것이다.

 

 

 

하지만, 이렇게 하면 문제가 생긴다. 

예를들어 스티커의 점수가 아래와 같이 되어있다고 하자.

 

 

 

아까의 방식대로 점수를 구한다면. 아래의 그림처럼 될 것이다.

 

이렇게 dp[1]을 활용하게 되면 꼴랑 60점밖에 못벌어간다.

그렇다면 최대값은 어떻게 하면 구할 수 있을까? 

이렇게 하면  30+60으로 90점을 벌어간다.

따라서 dp[2]는

dp[1]을 활용했을 때와 dp[1]을 활용하지 않았을 때의 두가지중 큰 값을 저장하면 된다.

 

그런데 이렇게 진행하다보면 DP를 진행하면서 많은 예외 상황들이 생기게 될것이고,

정상적인 답을 구할 수 없게 될 것이다.

당장 2열까지밖에 안했는데도 예외처리를 해줘야하니 말이다.

 

 

그래서 조금 다른 방법을 사용하기로 한다.

아래와 같이 열마다의 dp를 부여하는 것이 아닌

각 원소마다 dp를 저장하는 것이다.

이렇게 바꾼 후 한번 진행해보면 아래와 같이 된다.

 

dp[0][1]은 dp[1][0]과 본인의 스티커 값을 더한것이 저장하면 되고.

dp[1][1]은 dp[0][0]과 본인의 스티커 값을 더한것을 저장하면 된다.

본인의 스티커 값과 그 이전 열의 대각선 dp값을 합쳐서 저장한 것이다.

 

 

그러면 2열을 넘어 다음 DP의 과정도 진행해보자.

3열부터 나오는 예외를 아래의 예시와 함께 알아보자.

500이 잘 읽은거 맞아요.

이전과 같이 dp[1][2]를 구하려면, 이전 열의 대각선 dp값이랑 본인의스티커값을 더하면된다.

따라서 dp[0][1](30+10)+본인스티커(100)이므로 140이 나온다.

 

 

하지만 [0][0]에 저 압도적인 500이 보이는가? 저걸 넣으면 140은 생각도 안날것 같다.

그래서 이렇게 2열 전의 DP값(500)과 본인 스티커(100)을 더하여 600이라는 점수를 만들었다.

 

 

요약하자면, 

1열 전의 대각선 dp 값을 더하는 것보다 (30+10+100)

 

 

2열 전의 대각선 행의 dp 값을 더하는것이 더 크다면 (500+100)

 

 

2열전의 dp값을 더해주는 것이라는 예외처리를 해주면 되겠다.

 

설명만들으면 이해가 엄청나게 안갈테니 

백준이 준 예제를 통해 한번 시뮬레이션 해보길 바랍니다.

 

정답 코드

import sys
input = sys.stdin.readline
t=int(input())
for _ in range(t):
    stickers=[]
    n=int(input())
    for i in range(2):
        temp=list(map(int,input().split()))
        stickers.append(temp)
    
    dp=[[0 for i in range(n)],[0 for i in range(n)]]
    dp[0][0]=stickers[0][0]
    dp[1][0]=stickers[1][0]
    if n>1:
        dp[0][1]=dp[1][0]+stickers[0][1]
        dp[1][1]=dp[0][0]+stickers[1][1]

    for i in range(2,n):
        for j in range(0,2):
            a=dp[1-j][i-1]+stickers[j][i]
            b=dp[1-j][i-2]+stickers[j][i]
            dp[j][i]=max(a,b)
    print(max(dp[1][-1],dp[0][-1]))

정답 코드는 다음과 같습니다.

(상세 설명 예정) 

 

 

문제풀이 자가 피드백

dp에서도 여러 경우의 수 중 최대값으로 점화식을 구성  할 수 있다는 것을 알았다.

너무 많은 경우의 수가 나올때는 생각이 잘못되었는가를 다시 한번 생각해본다 (같은 행의 DP->원소마다 DP)

DP문제를 많이 풀어보자 (2시간 반 걸려서 답 참고하여 풀음..)