문제 출처 : www.acmicpc.net/problem/9465
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
문제 해석 : 스티커를 뜯으면 상하좌우로 모두 뜯긴다. 이때 최대 점수를 구할 수 있게 뜯는 문제이다.
문제 풀이 : DP로 풀 수 있는 문제이다. 갈 수 있는 방법은 자신과 다른 열의 바로전, 또는 2개전이며 이 중에서 최대 값을 구하면 되는 문제이다.
풀이 코드
T = int(input())
for test_case in range(T):
N = int(input())
arr = [list(map(int, input().split())) for _ in range(2)]
arr[0][1] = arr[0][1] + arr[1][0]
arr[1][1] = arr[1][1] + arr[0][0]
for k in range(2, N):
arr[0][k] = arr[0][k] + max(arr[1][k - 1], arr[1][k - 2])
arr[1][k] = arr[1][k] + max(arr[0][k - 1], arr[0][k - 2])
answer = max(arr[0][N-1], arr[1][N-1])
print(answer)author : donghak park
contact : donghark03@naver.com
## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.
'📊알고리즘, 문제풀이 > 📈문제풀이 (PS)' 카테고리의 다른 글
| [알고리즘][Python] 백준 15650 N과 M (2) 문제 풀이 (0) | 2021.01.26 |
|---|---|
| [알고리즘][Python] 백준 9663 N-Queen 문제 풀이 (0) | 2021.01.26 |
| [알고리즘][Python] 백준 5639 이진 검색 트리 문제 풀이 (0) | 2021.01.25 |
| [알고리즘][Python] 백준 2638 치즈 문제 풀이 (0) | 2021.01.25 |
| [알고리즘][Python] 백준 2263 트리의 순회 문제 풀이 (0) | 2021.01.24 |