문제 링크

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

문제 설명

• 2행 N열 보드가 주어진다
• 스티커마다 점수가 주어진다
• 한 스티커를 선택하면 인접한 스티커는 선택할 수 없다
• 점수의 최댓값 출력

풀이

• dp[0][0], dp[1][0], dp[0][1], ... 순서로 돌면서 점수 계산
• 어차피 위, 아래는 동시에 선택할 수 없기 때문에 나누어 생각한다
• 해당 좌표까지의 최댓값 저장
  
• 위쪽일 때
  • 해당 좌표를 선택할 경우
    • 왼쪽, 아래쪽은 선택할 수 없기 때문에 (왼쪽아래 까지의 최댓값) + (현재 스티커 점수)
  • 해당 좌표를 선택하지 않을 경우
    • max(왼쪽까지의 최댓값, 왼쪽아래까지의 최댓값)
• 아래쪽일 때
  • 해당 좌표를 선택할 경우
    • (왼쪽위까지의 최댓값) + (현재 스티커 점수)
  • 해당 좌표를 선택하지 않을 경우
    • max(왼쪽위까지의 최댓값, 왼쪽까지의 최댓값)

느낀 점

• 처음에 문제가 잘 이해가 안됐다
• 사용한다는게 무엇인지..
• 그냥 선택한다고 이해했다
• DP를 이용해야겠다고 생각은 들었는데 어떻게 구현해야 하는지 조금 고민이 됐다
• 반복문 순서를 행이 아닌 열을 우선으로 진행해야겠다고 생각했다

코드

import sys


def init():
    n = int(ipt())
    board = [list(map(int, ipt().split())) for _ in range(2)]
    dp = [[0] * n for _ in range(2)]
    dp[0][0] = board[0][0]
    dp[1][0] = board[1][0]
    return n, board, dp


ipt = sys.stdin.readline
tc = int(ipt())
for _ in range(tc):
    n, board, dp = init()
    for x in range(1, n):
        for y in range(2):
            if y % 2 == 0:
                dp[y][x] = max(
                    board[y][x] + dp[y+1][x-1], 
                    max(dp[y][x-1], dp[y+1][x-1])
                )
            else:
                dp[y][x] = max(
                    board[y][x] + dp[y-1][x-1], 
                    max(dp[y-1][x-1], dp[y][x-1])
                )
    print(max(map(max, dp)))