반응형
알고리즘 분류
- 다이나믹 프로그래밍
SOLUTION
import sys
T = int(sys.stdin.readline())
for _ in range(T):
N = int(sys.stdin.readline())
sticker = [list(map(int, sys.stdin.readline().split())) for _ in range(2)]
# 위에서 때는 경우, 아래서 때는 경우를 나눠서 구한다
for i in range(1, N):
# i가 1일때는 왼쪽 대각선에 붙어 있는 스티커는 때지지 않으므로 점수에 더한다
if i == 1:
sticker[0][i] += sticker[1][i-1]
sticker[1][i] += sticker[0][i-1]
else:
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]))
'코딩테스트 대비 > BOJ' 카테고리의 다른 글
[Baekjoon/Python] 16953번: A → B - 효과는 굉장했다! (0) | 2022.04.03 |
---|---|
[Baekjoon/Python] 11660번: 구간 합 구하기 5 - 효과는 굉장했다! (0) | 2022.04.03 |
[Baekjoon/Python] 1991번: 트리 순회 - 효과는 굉장했다! (0) | 2022.04.03 |
[Baekjoon/Python] 1932번: 정수 삼각형 - 효과는 굉장했다! (0) | 2022.04.03 |
[Baekjoon/Python] 1629번: 곱셈 - 효과는 굉장했다! (0) | 2022.04.03 |