백준 9465 스티커
문제
문제링크 : https://www.acmicpc.net/problem/9465
풀이전략
- 스티커와 인접한 부분은 사용할 수 없다. 그렇다고하여 항상 엇갈리게 뽑는 것이 아니다.
- 첫번째줄, 두번째줄, 아무것도 선택안되었을 때 3가지 케이스가 있고, 그 케이스에 따라 메모이제이션으르 해야한다. 그 값들 중 최대 값을 찾으면 된다.
코드
#include<bits/stdc++.h>
using namespace std;
#define mine
int a[3][100001];
int dp[3][100001];
int N;
int stiker(int n, int beforeCheck){
if(n>N) return 0;
int&ret = dp[beforeCheck][n];
if(ret != -1) return ret;
// beforeCheck = 1번줄 또는 2번줄인지 체크되고 아무것도 안되어있으면 0
// 서로 맞닿는 부분이 있는지 없는지, 없으면 그에 따라 최대값을 구하는 것이다.
for(int i=1; i<=2; i++){
if(i != beforeCheck){
ret = max(ret, stiker(n+1, i)+a[i][n]);
}
}
// 이전에 아무것도 없을 때는 항상 다음항을 탐색하므로 넣어준다.
ret = max(ret, stiker(n+1, 0));
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
// freopen("../input.txt","rt",stdin);
int T;
cin >> T;
for(int i=0; i<T; i++){
cin >> N;
memset(a, -1, sizeof(a));
memset(dp, -1, sizeof(dp));
for(int j=1; j<=2; j++){
for(int i=1; i<=N; i++){
cin >> a[j][i];
}
}
cout<<stiker(1, 0)<<endl;
}
return 0;
}
소감
이 문제에서 중요한 아이디어는 1번째, 2번째 줄 모두를 선택하지 않고 넘어갈 경우이다. 이러한 경우도 잊지않고 넣어주어야한다.
Author And Source
이 문제에 관하여(백준 9465 스티커), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gomster_96/백준-9465-스티커저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)