[백준9465] 스티커

문제

---

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

9465번: 스티커

 

생각의 흐름

---

동적프로그래밍의 핵심 1) 전체 과정 중 반복되는 작은 단계 찾기 2) 해당 단계에서의 최대 혹은 최소값 찾기 3) 갱신시켜가며 다음 단계에서의 최대 혹은 최소값 찾기 만 잘 기억하면 된다.

주어진 input이 위 문제 링크의 첫 번째 케이스라고 한다면 각 칸에 올 수 있는 최대수는 아래와 같다.

 

50	10+30=40	100+ max(100, 30)=200	20+ max(120, 100)=140	40+ max(210, 120)=250
30	50+50=100	70+ max(40, 50)=120	10+ max(200, 40)=210	60+ max(140, 200)=260

 

2열의 경우 단순히 왼쪽 대각선에 있는 수를 더해준 수가 오는 것이 최대이다. 하지만 3열부터는, 왼쪽 대각선 방향의 수와 그 수의 왼쪽에 있는 수 중에 max를 더해주는 것이 최대이다.

 

코드

---

# 백준9465
T = int(input())
for _ in range(T):
    n = int(input())
    sticker = []
    for i in range(2):
        sticker.append(list(map(int, input().split())))
    sticker[0][1] += sticker[1][0]
    sticker[1][1] += sticker[0][0]
    for i in range(2, n):
        sticker[0][i] += max(sticker[1][i-1], sticker[1][i-2])
        sticker[1][i] += max(sticker[0][i-1], sticker[0][i-2])
    print(max(sticker[0][n-1], sticker[1][n-1]))