[BOJ]9465. 스티커

문제

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

 

사용 알고리즘

DP

 

풀이

고려사항

이전 열(다른 행)의 스티커 가중치가 현재 가질 수 있는 스티커 가중치의 최대인지

 

후기

이 문제의 keypoint는 행이 2개로 고정되어 있으며 점수는 음수가 아닌 것이다.

점수가 음수가 아닌 이상 이전 2칸 이상을 고려하지 않아도 된다.

처음에는 현재 열이 j이면 0 ~ j-2까지의 리스트 전체에서 max값과 이전 열의 다른 행을 비교했다.

하지만 이건 불필요한 작업이였고 다른 행의 이전 2개만 비교하면 된다.

그 이전은 이후에 가중치가 음수가 아니기 때문에 하나라도 더 선택하는 것이 큰 값이 되기 때문이다.

 

코드

import sys
input = sys.stdin.readline

T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    stickers = [list(map(int, input().split())) for _ in range(2)]
    dp = [[0] * N for _ in range(2)]
    
    # 초기값 세팅
    dp[0][0], dp[1][0] = stickers[0][0], stickers[1][0]
    if N > 1:
        dp[0][1] = stickers[0][1] + dp[1][0]
        dp[1][1] = stickers[1][1] + dp[0][0]
        
    # 최대값 탐색
    for i in range(2, N):
        dp[0][i] = stickers[0][i] + max(dp[1][i - 1], dp[1][i - 2])
        dp[1][i] = stickers[1][i] + max(dp[0][i - 1], dp[0][i - 2])
    print(max(dp[0][N - 1], dp[1][N - 1]))

 

결과