[백준/파이썬] 9465번 스티커

solved.ac Class 4레벨에 속한 문제이다.

문제 주소: https://www.acmicpc.net/problem/9465

9465번: 스티커

문제 해석

스티커를 떼어내 최대의 점수를 얻어야 한다.

이때 스티커를 떼면 상하좌우에 존재하는 스티커가 함께 떼어지고, 함께 떼어진 스티커는 점수를 획득하지 못한다.

얻을 수 있는 최대의 점수를 구하는 문제이다.

문제 풀이

dp를 이용해서 해결해 주었다.

 

j열의 새로운 스티커를 선택할 때

1. j - 1열의 반대 행의 점수
2. j - 2열의 두 점수

위 점수중 최댓값 + 내 스티커의 점수를 합한 값이 최대 점수가 된다.

문제 코드

import sys
input = sys.stdin.readline

def solve(n, arr):
    dp = [[0] * (n + 1) for _ in range(2)]
    dp[0][1] = arr[0][0]
    dp[1][1] = arr[1][0]

    score = max(arr[0][0], arr[1][0])
    for j in range(2, n + 1):
        dp[0][j] = max(dp[1][j - 1], dp[0][j - 2], dp[1][j - 2]) + arr[0][j - 1]
        dp[1][j] = max(dp[0][j - 1], dp[1][j - 2], dp[0][j - 2]) + arr[1][j - 1]
        score = max(dp[0][j], dp[1][j], score)
    return score

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

제출 결과

n = 1인 경우 엣지케이스를 잘 확인하자..