[C++] 인형 전시 (백준 30645번)

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

 

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

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

    int r, c, n;
    cin >> r >> c >> n;

    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }

    sort(d.begin(), d.end());

    vector<int> maxh(c, 0);
    int idx = 0;
    int ans = 0;

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            while (idx < n && d[idx] <= maxh[j]) {
                idx++;
            }
            if (idx >= n) break;
            maxh[j] = d[idx++];
            ans++;
        }
        if (idx >= n) break;
    }

    cout << ans << '\n';
}

처음에 오름차순으로 정렬하고 작은 것부터 배치하면 되겠다는 생각까지는 했는데 n이 놓을 수 있는 칸의 수보다 크면 어떡하지? -> 서치 후 이미 해당 열에 배치한 인형과 높이가 같으면 전시하지 않아도 된다는 것을 깨달음..! (정답)