[BOJ] 9465 - 스티커 (C++)
문제
코드
#include <iostream>
using namespace std;
int dp[2][100001], arr[2][100001];
int T, N;
int solve(){
cin >> N;
for (int i = 0; i < N; i++) cin >> arr[0][i];
for (int i = 0; i < N; i++) cin >> arr[1][i];
dp[0][0] = arr[0][0];
dp[1][0] = arr[1][0];
dp[0][1] = arr[0][1] + dp[1][0];
dp[1][1] = arr[1][1] + dp[0][0];
for (int i = 2; i < N; i++){
dp[0][i] = arr[0][i] + max(dp[1][i-1], dp[1][i-2]);
dp[1][i] = arr[1][i] + max(dp[0][i-1], dp[0][i-2]);
}
return max(dp[0][N-1], dp[1][N-1]);
}
int main(void){
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> T;
while (T--){
cout << solve() << "\n";
}
}
접근
한 스티커를 사용하게 되면 주변 상하좌우의 스티커를 사용하지 못한다는 조건을 더 생각할 필요가 있었다. 2행 n열로 구성되기 때문에 아래와 같은 선택지들만 존재하는 것을 알 수 있다.
살펴보게 되면 1열의 원소들은 둘 중 하나 반드시 선택하게 되고 이후의 것들은 두 가지 경우로 분기하여 반복된다는 것을 알 수 있다. 이를 코드로 구현하였다.
Author And Source
이 문제에 관하여([BOJ] 9465 - 스티커 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@keybomb/BOJ-9465-스티커-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)