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

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 9465번 스티커
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

2행 n열 스티커에서 인접 제약을 지키며 얻을 수 있는 최대 점수를 구하는 문제입니다.

코드

import sys; read = sys.stdin.readline

for T in range(int(read())):
    n = int(read())
    stickers = [list(map(int, read().split())) for _ in range(2)]

    dp = [[0]*n for _ in range(2)]
    dp[0][0] = stickers[0][0]
    dp[1][0] = stickers[1][0]

    if n > 0:
        dp[0][1] = dp[1][0] + stickers[0][1]
        dp[1][1] = dp[0][0] + stickers[1][1]

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

설명

각 칸에서 가능한 이전 상태(대각선/한 칸 전/두 칸 전)를 고려해 DP로 최댓값을 누적합니다.

---

• 백준 문제풀이 전체 목록 보기

---