[solved.ac 실버1] 9465_스티커 (파이썬, DP)

제한 사항

문제

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

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

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

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

입력

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

 

출력

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

예제

---

나의 풀이

DP로 풀이했다. 처음에는 스티커를 뗐을 때 왼쪽, 오른쪽, 위, 아래 스티커를 사용할 수 없다는 조건 때문에 DP로 어떻게 풀어야 할 지 고민이 됐었는데 현재 위치보다 오른쪽의 스티커를 사용하지 못하는 것은 고려하지 않으니 어떻게 풀 지 감이 잡히기 시작했다.

DP는 메모이제이션이라는 기록하는 기법을 사용한다. 이 문제에서는 현재 열에서 얻을 수 있는 스티커 점수의 최댓값을 기록한다.

첫 번째 열

스티커

위와 같은 스티커가 있을 때 우선 맨 앞 열부터 순차적으로 확인한다.

맨 앞 열에서 선택할 수 있는 경우는 a행와 b행 중 하나이다.

dp table

(a, 1)번 스티커를 선택했을 때 10점을 얻을 수 있고, (b, 1)번 스티커를 선택했을 때 20점을 얻을 수 있다. 이를 dp table에 기록한다.

두 번째 열

a행을 선택했을 때는 이전 열의 b행 값과 더한 것이, b행을 선택했을 때는 이전 열의 a행 값과 더한 것이 최대 점수가 될 것이다. (변을 마주하고 있으면 스티커를 사용할 수 없다는 조건을 기억하라)

두 번째 열까지 채워진 dp table은 위와 같은 모습일 것이다.

세 번째 열

세 번째 열 부터는 dp table을 활용해야 한다. 이전에 구해놓은 해당 위치까지의 최대 값을 사용하기 위해서이다.

a 행을 구해야 한다면 이전 열의 b행 값과 2개 전 열의 b행 값 중 큰 값을 선택해야 한다.

왜냐하면 우선 (b, 2) 위치는 현재 위치(a, 3)를 뗐을 때 영향을 받지 않는 위치이고, 그 왼쪽인 (b, 1)과 비교하는 이유는 (b, 2)와 독립적인 위치이기 때문이다. (a, 1)의 경우 (b, 2)와 대각선에 위치하기 때문에 (b, 2)의 값이 선택될 때 영향을 줄 수 있는 자리이다. 그러나 (b, 2)와 (b, 1)은 둘 다 동시에 사용할 수 없는 위치이다 보니 독립적이라고 할 수 있다.

3열까지 구하면 위와 같은 모습이 된다.

네 번째 열

세 번째 열과 마찬가지의 작업을 한다. 이 작업은 끝까지 동일하게 진행된다.

다섯 번째 열

여섯 번째 열

마지막 열

마지막 열까지 세 번째 열에서 설명한 작업이 수행되면 dp table이 완성된다.

두 값 중 290이 구할 수 있는 스티커의 최대 값이 된다.

 

전체 코드

for _ in range(int(input())):
    n = int(input())
    sticker = [list(map(int, input().split())) for _ in range(2)]
    dp = [[0] * n for _ in range(2)]
    dp[0][0], dp[1][0] = sticker[0][0], sticker[1][0]
    if n >= 2:
        dp[0][1], dp[1][1] = dp[1][0] + sticker[0][1], dp[0][0] + sticker[1][1]
    for i in range(2, n):
        dp[0][i] = sticker[0][i] + max(dp[1][i - 1], dp[1][i - 2])
        dp[1][i] = sticker[1][i] + max(dp[0][i - 1], dp[0][i - 2])
    print(max(dp[0][n-1], dp[1][n-1]))

채점 결과