백준_9465_스티커

문제

9465번: 스티커

풀이

첫번째 열에 속하는 두 값을 제외하고 연산을 시작한다. 제한사항에 따르면 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 함께 사용할 수 없다. 이 조건을 이용하여 왼쪽에서 오른쪽으로 진행하면서 max(왼쪽 대각선 값+현재 값, 왼쪽값)을 연산하였다. 

# 초기상태
[50, 10, 100, 20, 40]
[30, 50, 70, 10, 60]

# n = 1
[50, 50, 100, 20, 40]
[30, 100, 70, 10, 60]

# n = 2
[50, 50, 200, 20, 40]
[30, 100, 120, 10, 60]

# n = 3
[50, 50, 200, 200, 40]
[30, 100, 120, 210, 60]

# n = 4
[50, 50, 200, 200, 250]
[30, 100, 120, 210, 260]

코드

T = int(input())
for t in range(T) :
    n = int(input())
    board = [list(map(int, input().split())) for i in range(2)]
    for j in range(1, n) :
        board[0][j] = max(board[0][j]+board[1][j-1], board[0][j-1])
        board[1][j] = max(board[1][j]+board[0][j-1], board[1][j-1])
    print(max(board[0][-1], board[1][-1]))

다른 사람들의 코드를 찾아보니, 아래와 같은 풀이방식이 이해하기 쉽게 느껴졌다.

T = int(input())

for t in range(T):
    n = int(input())
    arr1 = list(map(int, input().split()))
    arr2 = list(map(int, input().split()))

    arr1[1] += arr2[0]
    arr2[1] += arr1[0]

    for j in range(2, n):
        arr1[j] += max(arr2[j-1], arr2[j-2])
        arr2[j] += max(arr1[j-1], arr1[j-2])

    print(max(arr1[-1], arr2[-1]))

"""
# 처음 상태
[50, 10, 100, 20, 40]
[30, 50, 70, 10, 60]

# n = 1
[50, 40, 100, 20, 40]
[30, 100, 70, 10, 60]

# n = 2
[50, 40, 200, 20, 40]
[30, 100, 120, 10, 60]

# n = 3
[50, 40, 200, 140, 40]
[30, 100, 120, 210, 60]

# n = 4
[50, 40, 200, 140, 250]
[30, 100, 120, 210, 260]
"""