[백준 9465번] 스티커 (C++)

https://www.acmicpc.net/problem/9465

9465번: 스티커

딱봐도 DP문제이다.

실버DP문제는 꽤 많이 풀어서 그런지 풀이가 한눈에 보인다.

해당 스티커를 선택할 수 있는 경우를 모두 고려해서 최대값을 dp값으로 저장하면 된다.

위의 경우를 점화식으로 작성하기만하면 끝이다.

스티커가 2줄이라 2차원 배열 쓰면 끝.

코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#define endl "\n"

using namespace std;
int main(){
  int T,n;
  cin >> T;
  while(T--){
    cin >> n;
    int dp[2][100001];
    int first_line[100001];
    int second_line[100001];
    for(int i = 0 ; i < n; i++){
      cin >> first_line[i];
    }
    for(int i = 0 ; i < n; i++){
      cin >> second_line[i];
    }

    dp[0][0] = first_line[0];
    dp[1][0] = second_line[0];
    dp[0][1] = dp[1][0] + first_line[1];
    dp[1][1] = dp[0][0] + second_line[1];
    for(int i = 2; i < n; i++){
      dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + first_line[i];
      dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + second_line[i];
    }

    int ans = max(dp[0][n-1], dp[1][n-1]);
    cout << ans << endl;
  }
}

 

 

 

 

 

위의 헤더파일 가져온 것들은 문제를 풀다보니 쌓인 건데 때마다 include하기가 귀찮아서 그냥 놔두었다.