[백준9465] 스티커 (C++)
#include <iostream>
#include<algorithm>
using namespace std;
int a[3][100001];
int d[3][100001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= n; j++)
cin >> a[i][j];
}
d[0][0] = 0; d[1][0] = 0; d[2][0] = 0;
for (int k = 1; k <= n; k++) {
d[0][k] = max({ d[0][k - 1], d[1][k - 1], d[2][k - 1] });
d[1][k] = max(d[0][k - 1], d[2][k - 1]) + a[1][k];
d[2][k] = max(d[0][k - 1], d[1][k - 1]) + a[2][k];
}
cout << max({ d[0][n], d[1][n], d[2][n] }) << '\n';
}
return 0;
}
재귀함수를 이용한 TOP-DOWN 방식을 적용했을 땐 시간초과가 났다. 질문답변 글을 읽어보니, dp[3][100001]을 0으로 초기화했을 때 메모이제이션이 작동하지 않는 경우가 생기기 때문이라고 한다. 이 부분에 대해선 내일 다시 공부해봐야겠다.
📌아이디어
d[0][k]는 k번째에서 스티커를 떼지 않을 경우, d[1][k]는 위쪽 스티커 한 장을 뗄 경우, d[2][k]는 아래쪽 스티커 한 장을 뗄 경우의 최대 점수를 저장한 배열이다.
인접한 스티커를 떼면 안 된다는 조건이 있으므로, d[1][k]는 d[0][k] 또는 d[2][k]의 최댓값에 a[1][k]를 더해주면 된다. d[2][k]의 경우도 마찬가지이다. d[0][k]의 경우 스티커를 떼지 않은 상태이므로 d[0][k-1], d[1][k-1], d[2][k-2] 중에서 최댓값을 가진다.
Author And Source
이 문제에 관하여([백준9465] 스티커 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoohoo030/백준9465-스티커-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)