https://www.acmicpc.net/problem/9465
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
이문제의 거의 다풀어놓고 위에 배열크기를 잘못 설정해서 계속 틀렸다. 진짜 알고리즘 문제 풀면서 항상 느끼는 거지만 배열의 크기에서 오타나면 항상 틀리는 거같다 이문제의 경우 총 2가지의 케이스를 생각해줄 수 있다
자 40을 예시로 들면 자기이전에 변을 맞대지 않는애들 고르면 자동적으로 2번째거 이전 위에거가 선택 된다
2번째거 이전에 반대쪽애를 선택해주면 3번째거 이전에 위에거 가 선택 된다 이렇게 짠이유는 이전꺼 아래거와 2번째전거 위에거 더한게 2번째거 전에 거와 3번째전에거의 위에거의 합이 더 클 수 있기 때문이다 이에 이 문제의 점화식은
dp[l][0]=max(dp[l - 1][1] + card[l][0], dp[l - 2][1] + card[l][0])
이렇게 맨마지막에 위에거를 선택했을 때와
dp[l][1]=max(dp[l - 1][0] + card[l][1], dp[l - 2][0] + card[l][1])
이렇게 맨마지막에 아래거를 선택 했을 때 2개가 존재한다
#include <iostream>
#include <algorithm>
int dp[100001][2];
int card[100001][2];
using namespace std;
int main() {
int T;//테스트케이스
int n;//해당하는 스티커의 점수
cin >> T;
for (int i = 0; i < T; i++) {
cin >> n;
for (int j = 0; j < 2; j++) {
for (int k = 1; k <= n; k++) {
cin >> card[k][j];
}
}
dp[1][0] = card[1][0];
dp[1][1] = card[1][1];
for (int l = 2; l <= n; l++) {
dp[l][0] = max(dp[l - 1][1] + card[l][0], dp[l - 2][1] + card[l][0]);
dp[l][1] = max(dp[l - 1][0] + card[l][1], dp[l - 2][0] + card[l][1]);
}
cout << max(dp[n][0], dp[n][1])<<'\n';
}
}