백준 2240번 자두나무[C++]

1. 문제 풀이

문제의 유형은 dynamic programming입니다. 테이블은 아래와 같이 정의했습니다.

 

d[i][j] = k : i 번 이동 후 j초가 지났을 때 먹을 수 있는 자두의 개수 k

 

이렇게 테이블을 세우고 d[i][j]를 갱신하자고 해봅시다. 그렇다면 고려할 수 있는 상황은 두 가지입니다.

 

이동한 경우: d[i-1][j-1]

이동하지 않은 경우 : d[i][j-1]

 

두 값 중 최댓값을 선택한 다음 j초의 자두가 떨어지는 나무의 번호를 확인하여 1을 더해주시면 됩니다. 여기서 초기 위치가 1번 나무였기 때문에 이동한 횟수가 짝수이면 1번 나무에 위치한 것이고 홀수라면 2번 나무에 위치해 있다는 사실을 알 수 있습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';
int t, w, a[1005], d[1005][35];
int main() {
  fastio(nullptr, false);
  cin >> t >> w;
  for(int i = 1; i <= t; i++){
    cin >> a[i];
    d[i][0] = d[i-1][0];
    if(a[i]&1) d[i][0]++;
  }
  for(int j = 1; j <= w; j++){
    for(int i = 1; i <= t; i++){
      d[i][j] = max(d[i-1][j], d[i-1][j-1]);
      if((a[i]&1) && !(j&1)) d[i][j]++;
      else if(!(a[i]&1) && j&1 ) d[i][j]++;
    }
  }
  cout << *max_element(d[t], d[t]+w+1);
}

 

3. 제출 결과