백준 9465 스티커
by 진혀크
문제
- 2행 n열로 배치되어있는 2n개의 스티커를 떼어낸다. 떼어낼 수 있는 스티커 점수의 최대값을 구하라
입력
- 첫째 줄에 테스트 케이스 T가 주어지며 각 테스트 케이스의 첫 번째 줄에는 n 그 다음에는 n개의 배열이 2번 주어진다.
출력
예제 입력
2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80
예제 출력
260
290
접근
- 다이나믹 프로그래밍을 어떻게 사용할까?
내가 생각한 풀이
- 각 스티커에 접근 할 수 있는 칸은 어디어디인가?
- 한 칸 떨어진 대각선에 위치한 스티커와 2칸 떨어진 스티커 2장이 원하는 스티커에 접근 할 수 있는 스티커들이다!
- 저 위치에 있는 스티커들의 누적값 + 현재 스티커의 값 중에 최대값을 찾아서 dp 배열에 저장해주면 된다.
- index로 따지면 [i][0]에는 [i-1][1], [i-2][0], [i-2][1]이 접근 할 수 있다.
코드
#include<iostream>
using namespace std;
int main(void){
int iter;
cin>>iter;
for(int i = 0 ;i<iter;i++){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int c, m = -1, n[100002][2], dp[100002][2] ={0, };
cin>>c;
for(int j = 1 ;j<=c;j++){
cin>>n[j][0];
}
for(int j = 1 ;j<=c;j++){
cin>>n[j][1];
}
dp[1][0] = n[1][0]; dp[1][1] = n[1][1];
for(int j = 2 ;j<=c;j++){
dp[j][0] = max(dp[j-1][1],max(dp[j-2][0],dp[j-2][1]))+n[j][0];
dp[j][1] = max(dp[j-1][0],max(dp[j-2][0],dp[j-2][1]))+n[j][1];
}
cout<<max(dp[c][0],dp[c][1])<<endl;
}
return 0;
}
Subscribe via RSS