Codeforces #1469B Red and Blue

문제

https://codeforces.com/problemset/problem/1469/B

걸린 시간

01 : 00 : 06

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n, m;
        cin >> n;
        vector<int> r(n);
        for(auto& i : r) cin >> i;
        vector<int> rpS(n);
        rpS[0] = r[0];
        int maxr = max(0, r[0]);
        for(int i = 1; i < n; i++){
            rpS[i] = rpS[i-1] + r[i];
            maxr = max(maxr, rpS[i]); 
        }
        cin >> m;
        vector<int> b(m);
        for(auto& i : b) cin >> i;
        vector<int> bpS(m);
        bpS[0] = b[0];
        int maxb = max(0, b[0]);
        for(int i = 1; i < m; i++){
            bpS[i] = bpS[i-1] + b[i];
            maxb = max(maxb, bpS[i]); 
        }
        cout << maxr+maxb << "\n";
    }
    return 0;
}

작은 입력에서의 경우의 수를 보고 생각보다 많지 않은데? 하며 백트래킹으로 구현했다가 시간초과를 받았다;

f(a) 의 계산 방식을 봐선 top-down dp 로는 풀 수 없어 보였고 남은 시간 동안 greedy 한 방법이 있을까 생각을 하다 보니 r, b 각각의 최대값의 합이 문제 전체의 최대값이 아닐까 싶다는 생각이 들었다. r, b 배열은 기존의 순서를 지키며 자유롭게 배치해야 하므로 어느 색깔이 먼저 오느냐는 중요하지 않고 f(a) 값이 최대가 될 수 있게끔 하는 각각의 원소 집합을 찾으면 된다.

문제는 배열 a 를 이미 r, b 둘로 나뉘어 주어졌기 때문에 문제를 더 작은 조각들로 나누어 해결해보겠다는 생각을 일찍하지 못했다.

예제를 풀어서 떠오른 아이디어라기보단, 여러 문제를 풀며 조금은 높아진 직관 때문에 발견할 수 있었던 것 같다.