[백준] 9465 스티커

백준 9465 스티커

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다.

스티커는 2행 n열로 배치되어 있고 상냥이는 이 스티커를 이용해 책생을 꾸미려 한다.

상냥이가 구매한 스티커의 품질이 좋지 않아 스티커 한 장을 때면 그 스티커와 변을 공유하는 스티커는 모두 찢어져 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게 된 상냥이는 각 스트커에 점수를 매겨 점수의 합이 최대가 되도록 스티커를 떼려 한다.

가장 높은 스티커 집합의 점수를 구하시오.

입력

• 첫 번째 줄: 테스트 케이스의 개수 T
• 테스트 케이스 당
  • 첫 번째 줄:2n
  • 두, 세 번째 줄: 스티커들의 점수

출력

스티커 점수의 최댓값

해결 방식

dp 문제

• dp 배열에 현재 선택할 수 있는 스티커 점수의 최대 점수를 저장

과정

스티커 점수 배열

1. dp[0][1], dp[1][1]
   • dp[0][1] += dp[1][0] : dp[0][1] = 40 -dp[1][1] += dp[0][0] : dp[1][1] = 100
2. dp[0][2], dp[1][2] 계산
   • dp[0][2]
     • 대각선 아래 또는 대각선 아래의 옆칸만 사용 가능
     • dp[1][1] 또는 dp[1][0] 사용 가능
     • 30 vs 100 = 100점짜리 스티커 선택
     • dp[0][2] = 100+100 = 200
   • dp[1][2]
     • 대각선 위 또는 대각선 위의 옆칸만 사용 가능
     • dp[0][1] 또는 dp[0][0] 사용 가능
     • 40 vs 50 = 50점짜리 스티커 선택
     • dp[1][2] = 50+70 = 120
3. dp[0][3], dp[1][3] 계산
   • dp[0][3]
     • 대각선 아래 또는 대각선 아래의 옆칸만 사용 가능
     • dp[1][2] 또는 dp[1][1] 사용 가능
     • 120 vs 100 = 120점짜리 스티커 선택
     • dp[0][3] = 20+120 = 140
   • dp[1][3]
     • 대각선 위 또는 대각선 위의 옆칸만 사용 가능
     • dp[0][2] 또는 dp[0][1] 사용 가능
     • 200 vs 40 = 200점짜리 스티커 선택
     • dp[1][3] = 10+200 = 210
4. dp[0][4], dp[1][4] 계산
   • dp[0][4]
     • 대각선 아래 또는 대각선 아래의 옆칸만 사용 가능
     • dp[1][3] 또는 dp[1][2] 사용 가능
     • 210 vs 120 = 210점짜리 스티커 선택
     • dp[0][3] = 40+210 = 250
   • dp[1][4]
     • 대각선 위 또는 대각선 위의 옆칸만 사용 가능
     • dp[0][3] 또는 dp[0][2] 사용 가능
     • 140 vs 200 = 200점짜리 스티커 선택
     • dp[1][3] = 60+200 = 260
5. 마지막 두 칸(dp[0][4], dp[1][4]) 중 더 큰 값 출력
   • 260

코드

t = int(input())

for _ in range(t):
    n = int(input())
    dp = [list(map(int, input().split())) for _ in range(2)]

    for i in range(1, n):
        if i == 1:
            dp[0][1] += dp[1][0]
            dp[1][1] += dp[0][0]
            continue
        dp[0][i] += max(dp[1][i-1], dp[1][i-2])
        dp[1][i] += max(dp[0][i-1], dp[0][i-2])
    print(max(dp[0][-1], dp[1][-1]))