https://www.acmicpc.net/problem/9465
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
접근
RGB문제와 유사한 문제여서 매우 쉽게 풀었다.
스티커를 떼면 상하좌우에 있는 스티커들은 쓸 수가 없다. 최대한 많은 가치의 스티커를 떼어보자는 거다.
왼쪽부터 스티커를 뜯는다고 생각하자. 직전에 어떻게 뜯었냐에 따라 다음 스티커의 운명이 정해진다.
직전에 아래쪽 스티커를 떼어냈다면 다음 열의 아래쪽 스티커는 뜯을 수 없다.
따라서, 윗쪽 스티커를 떼어내기 또는 스티커를 떼지 않는 선택 두 가지밖에 없다.
직전에 윗쪽 스티커를 떼어냈다면 다음 열의 윗쪽 스티커는 뜯을 수 없다.
따라서, 아래쪽 스티커를 떼어내기 또는 스티커를 떼지 않는 선택 두 가지밖에 없다.
직전에 아무 스티커도 떼지 않았다면 다음 열의 어느 스티커든지 뜯을 수 있다.
따라서, 윗쪽 스티커를 떼어내기 또는 아래쪽의 스티커를 떼어내기 또는 아무 스티커도 떼지 않는 선택 세 가지밖에 없다.
가능한 행동이 3가지나 되므로 dp배열을 3행 n열로 만들어 각 행동에 대해 최대값을 누적시키면서 찾아나가면 된다.
#include <iostream>
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
int main() {
int T;
scanf("%d", &T);
for (int cases = 1; cases <= T; cases++) {
int N, dp[3][100001]{0}, arr[2][100001]{0};
scanf("%d", &N);
for (int i = 0; i < 2; i++) {
for (int j = 1; j <= N; j++) {
scanf("%d", &arr[i][j]);
}
}
for (int i = 1; i <= N; i++) {
dp[0][i] = MAX(dp[1][i - 1], dp[2][i - 1]) + arr[0][i];
dp[1][i] = MAX(dp[0][i - 1], dp[2][i - 1]) + +arr[1][i];
dp[2][i] = MAX(dp[0][i - 1], MAX(dp[1][i - 1], dp[2][i - 1]));
}
printf("%d\n", MAX(dp[0][N], MAX(dp[1][N], dp[2][N])));
}
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
1500 최대 곱 (1) | 2022.09.20 |
---|---|
1059 좋은 구간 (0) | 2022.09.18 |
2502 떡 먹는 호랑이 (0) | 2022.09.07 |
1876 튕기는 볼링공 (0) | 2022.09.06 |
4105 유클리드 (0) | 2022.09.05 |
댓글