728x90
반응형
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
👩🏻💻 코드
import sys
T = int(sys.stdin.readline().rstrip())
for _ in range(T):
n = int(sys.stdin.readline().rstrip())
dp = [[0 for col in range(n + 1)] for row in range(2)]
possible = [[True for col in range(n + 1)] for row in range(2)]
num = [list(map(int, sys.stdin.readline().rstrip().split())) for row in range(2)]
dp[0][0] = num[0][0]
dp[1][0] = num[1][0]
if n > 1:
dp[0][1] = dp[1][0] + num[0][1]
dp[1][1] = dp[0][0] + num[1][1]
for col in range(2, n):
dp[0][col] = max(dp[1][col - 2], dp[1][col - 1]) + num[0][col]
dp[1][col] = max(dp[0][col - 2], dp[0][col - 1]) + num[1][col]
print(max(dp[0][n - 1], dp[1][n - 1]))
📝 정리
- col 씩 이동하면서 col-1과 col-2의 대각선 칸의 max를 구한다.
- max와 현재 칸을 더하여 dp에 저장한다.
- 마지막 col에서 max를 구한다.
재채점 결과가 바뀌었길래 다시 봤더니 n이 1인 경우를 처리해주지 않아서였다. 매우 기본적인 걸 그냥 지나쳤다니 반성하자,,
728x90
반응형