[C++] 콘센트 (백준 7774번)

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

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> mul1(n);
    vector<int> mul2(m);

    for (int i = 0; i < n; i++) cin >> mul1[i]; // a 플러그 -> b 콘센트
    for (int i = 0; i < m; i++) cin >> mul2[i]; // b 플러그 -> a 콘센트

    sort(mul1.begin(), mul1.end());
    sort(mul2.begin(), mul2.end());

    int acnt = 1;
    int bcnt = 0;
    int idx1 = n - 1;
    int idx2 = m - 1;

    while (idx2 >= 0) {
        // mul1 (b 콘센트를 여러개 갖는 멀티탭) 하나 꽂기
        if (idx1 >= 0) {
            acnt--;
            bcnt += mul1[idx1];
            idx1--;
        } else {
            break;
        }
        // mul2 (a 콘센트를 여러개 갖는 멀티탭) 꽂을 수 있는 만큼 꽂기
        while (bcnt > 0 && idx2 >= 0) {
            bcnt--;
            acnt += mul2[idx2];
            idx2--;
        }
    }

    cout << acnt << '\n';
}

그리디 냄새가 폴폴.. A 콘센트, A 플러그, B 콘센트, B 플러그... 완전 헷갈려서 뇌에 힘을 빡줘야함.

 

일단 다음과 같이 정의해보자.

 

멀티탭1: A 플러그와 여러 개의 B 콘센트를 가지는 멀티탭

멀티탭2: B 플러그와 여러 개의 A 콘센트를 가지는 멀티탭

 

A 콘센트에 멀티탭1을 꽂으면? A 콘센트 개수는 하나 감소, B 콘센트 개수는 멀티탭 크기만큼 증가.

B 콘센트에 멀티탭2를 꽂으면? B 콘센트 개수는 하나 감소, A 콘센트 개수는 멀티탭 크기만큼 증가.

 

우리의 목표는 A 콘센트의 개수를 최대화하는 것이기 때문에 멀티탭2를 가능한 많이 쓰되, 멀티탭1은 가능한 최소로 사용해야 한다.

 

그래서 멀티탭1을 하나 추가한 후, 그렇게 생긴 B 콘센트에 가능한 최대로 멀티탭2를 추가하고... 이 과정을 반복해야 한다. 이 때 멀티탭들은 전부 내림차순 정렬되어있어야 한다. (즉, 멀티탭 크기가 큰 것들부터 사용해야 한다.)

 

(AC)