baekjoon 9465:스티커

baekjoon 9465 스티커

9465번 스티커

접근

지금 스티커를 놓아야 할 자리와 (column number), 직전 column에서 위에 스티커가 있는지
아래 스티커가 있는지 여부로 dp를 만들었다.

코드

//9465
#include <iostream>
#include <vector>
#include <array>
using namespace std;
array<array<int, 100000>, 3> cache;
int dp(int status, int cur, int n, vector<vector<int>>& v);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin >> t;
  while(t--){
    int n; cin >> n;
    vector<vector<int>> v(2, vector<int>(n));
    for(int i = 0; i < n; i++) cin >> v[0][i];
    for(int i = 0; i < n; i++) cin >> v[1][i];
    fill(cache[0].begin(), cache[0].begin()+n, -1);
    fill(cache[1].begin(), cache[1].begin()+n, -1);
    fill(cache[2].begin(), cache[2].begin()+n, -1);

    
    
    cout << dp(0, 0, n, v) << '\n';
  }
  return 0;
}
int dp(int status, int cur, int n, vector<vector<int>>& v){
  if(cur == n) return 0;
  int& ret = cache[status][cur];
  if(ret != -1) return ret;
  ret = 0;
  if(status == 0){
    ret = max(ret, dp(1, cur+1, n, v)+v[0][cur]);
    ret = max(ret, dp(2, cur+1, n, v)+v[1][cur]);
  }
  else if(status == 1){
    ret = max(ret, dp(0, cur+1, n, v));
    ret = max(ret, dp(2, cur+1, n, v)+v[1][cur]);
  }
  else if(status == 2){
    ret = max(ret, dp(0, cur+1, n, v));
    ret = max(ret, dp(1, cur+1, n, v)+v[0][cur]);
  }
  return ret;
  
}

배운 점

기초적인 dp 문제였다.