백준 2229번 조 짜기[C++]

1. 문제 풀이

  함수 solve(int cur)에서 md변수를 선언한 다음, [ md, cur ]까지를 조원으로 결정한 경우와 solve(md - 1)의 반환값을 더해 그중 최댓값을 찾아 테이블에 저장하는 방법을 사용하여 풀이했습니다.

 

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 n;
vi students;
int d[1005];

int solve(int cur) {
    if(cur < 0) {
        return 0;
    }

    if(d[cur] != -1) {
        return d[cur];
    }

    int mx, mn;
    mx = mn = students[cur];
    for(int md = cur; md >= 0; md--) {
        mx = max(mx, students[md]);
        mn = min(mn, students[md]);
        d[cur] = max(d[cur], solve(md - 1) + mx - mn);
    }
    
    return d[cur];
}

int main() {
    fastio(nullptr, false);

    cin >> n;
    for(int i = 0; i < n; i++) {
        int score;
        cin >> score;
        students.pb(score);        
    }    

    memset(d, -1, sizeof(d));

    cout << solve(n - 1);
}

 

3. 제출 결과