[BOJ] C++ 그리디 알고리즘 문제풀이 (3)

🧨 백준 1946번

문제 출처 : 백준 1946번 - 신입사원

문제 난이도 : 실버1

문제 링크 : www.acmicpc.net/problem/1946

1946번: 신입 사원

🧨 알고리즘 선택 및 C++ 코드

이 문제 자체를 이해하는 게 힘들었다. 정확히 얘기하자면 선발된 지원자들 안에서 조건을 따지는게 아니라 지원자들 전체에서 조건을 모두 따져서 서류와 면접 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발하는 것이다. 다시 말해, 매 지원자에 대해 모든 지원자와 서류, 면접 순위를 비교하고 한 사람에게라도 서류, 면접을 완벽하게 밀리면 선발되지 않는 것이다. 문제 이해가 힘들었지만 손으로 그리면서 예시 입출력을 따져보니 로직은 생각보다 쉬웠다. 

일단 서류 순위 - 면접 순위 순서로 전체 지원자를 정렬한다. 이때 맨 첫번째 지원자는 모든 지원자들에 비해 서류에서 우수하므로 무조건 합격이다. 서류는 정렬된 상태이므로 내가 항상 뒷사람보다 우수하다. 그럼 이때 따져보아야 할 것은 면접 순위이다. 만약 내가 앞 사람보다 서류는 낮지만 면접이 높으면 합격인 것이다. (이때 순위가 높은건 1등에 가까운 것을 말함) 그래서 전체 정렬 한번, 이전 사람과 내 면접 순위 비교로 간단하게 풀 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    
    for(int i = 0; i < t; i++) {
        int n;
        cin >> n;
        
        vector<pair<int, int>> applicant(n);
        for(int j = 0; j < n; j++) {
            cin >> applicant[j].first >> applicant[j].second;
        }
        sort(applicant.begin(), applicant.end());
        
        int sum = 1;
        int target = applicant[0].second;
        for(int k = 1; k < n; k++) {
            if(target > applicant[k].second) {
                target = applicant[k].second;
                sum++;
            }
        }
        cout << sum << '\n';
    }
}

---

 

🧨 백준 11000번

문제 출처 : 백준 11000번 - 강의실 배정

문제 난이도 : 골드5

문제 링크 : www.acmicpc.net/problem/11000

11000번: 강의실 배정

🧨 알고리즘 선택 및 C++ 코드

일단 강의 시작시간을 기준으로 정렬해야한다. (끝나는 시간으로 비교하면 안 됨) 2개의 배열이 필요한데, 하나는 각 강의실의 끝나는 시간이 기록된 배열과, 또 하나는 모든 강의의 시작과 끝나는 시점을 저장한 배열이다.

1) 모든 강의의 시작시간과 각 강의실의 끝나는 시간을 비교하면 된다고 생각해 이중 루프로 비교와 정렬을 반복해 구현했으나 시간초과가 떴다.. 단순히 이중 루프가 시간을 많이 잡아먹었다기 보다는 정렬이 문제였다. 정렬을 줄이려면 반복문을 1단 짜리로 바꿔야한다. 나름 push와 pop을 이용해보려 했으나 어쨌거나 정렬이 필요했다. (정렬로 가장 작은 값을 찾아야 한다)

2) 정렬을 줄이려면 삽입되자마자 정렬이 자동으로 되는 자료구조를 써야했는데 C++에서 그런 자료구조가 있는지 잘 몰랐기에 문제의 힌트를 봤다. 힌트는 자료구조, 그리디 알고리즘, 정렬, 우선순위 큐 로 사용할 알고리즘과 자료구조가 담겨있었는데 다른 건 다 사용하고 있었고, 우선순위 큐를 추가해주면 된다. 우선순위 큐(priority_queue)에 대해서는 간단한 자료구조라서 금방 찾아보고 넘어갔다. 다음에.. 언젠가.. 자료구조 파트도 정리할 기회가 있길 바란다.

어쨌거나 우선순위 큐(오름차순으로)를 사용한 덕분에 정렬은 초기 한 번만 하면 되었다. 큐의 top 원소와 비교하면 되는 것이 핵심인 거 같다. 아마 이 문제의 시간복잡도는 nlogn 정렬 한번이 포함(sort함수)되니 nlogn이라고 판단해본다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    
    priority_queue<int, vector<int>, greater<int>> room;
    vector<pair<int, int>> lecture(n);
    
    for(int i = 0; i < n; i++) {
        scanf("%d %d", &lecture[i].first, &lecture[i].second);
    }
    
    sort(lecture.begin(), lecture.end());
    room.push(lecture[0].second);
     
    for(int i = 1; i < n; i++) {
        if(room.top() <= lecture[i].first) {
            room.pop();
            room.push(lecture[i].second);
        } 
        else {
            room.push(lecture[i].second);
        }
    }
    
    printf("%d", room.size());

    return 0;
}

골드는 거의 풀어본 적이 없는데.. 무턱대고 도전해봤지만 나쁘지않게 풀어냈다. 자료구조 공부하자!

---

🧨 백준 1931번

문제 출처 : 백준  1931번 - 회의실

문제 난이도 : 실버2

문제 링크 : www.acmicpc.net/problem/1931

1931번: 회의실 배정

🧨 알고리즘 선택 및 C++ 코드

같은 그리디 문제여도 확실히 난이도가 있음을 느꼈다. 처음에는 회의 시작시간을 기준으로 정렬해야 된다고 생각했는데 어쨌거나 회의실에서 할 수 있는 회의의 최대 수를 구하는 문제이므로 회의 종료시간을 기준으로 오름차순 정렬해야 했다. 시작시간을 기준으로 정렬해서 코드를 짜보니 87% 부근에서 '틀렸습니다'로 채점되었다. 아마 일부 반례를 만족시키지 못하는 것 같았다. 그래서 그리디 문제답게 회의 종료시간을 기준으로 정렬한 결과 통과할 수 있었다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

// b - a 순으로 오름차순
bool compare(pair<int, int> a, pair<int,int> b) {
    if(a.second == b.second) {
        return a.first < b.first;
    }
    else {
        return a.second < b.second;
    }
}

int main()
{
    int N;
    cin >> N;
    
    vector<pair<int, int>> meeting(N);
    for(int i = 0; i < N; i++) {
        cin >> meeting[i].first >> meeting[i].second;
    }
    sort(meeting.begin(), meeting.end(), compare);

    int sum = 1;
    int start = meeting[0].first;
    int end = meeting[0].second;
    for(int i = 1; i < N; i++) {
        // 다음 시간대 회의로 넘어간다
        if(end <= meeting[i].first) {
            start = meeting[i].first;
            end = meeting[i].second;
            sum++;
        }
    }
    
    printf("%d", sum);
}

---

🧨 백준 12845번

문제 출처 : 백준 12845번 - 모두의 마블

문제 난이도 : 실버3

문제 링크 : www.acmicpc.net/problem/12845

12845번: 모두의 마블

🧨 알고리즘 선택 및 C++ 코드

일단 위의 문제들에 비해 굉장히 간단하게 풀었다. 역시나 그리디 알고리즘을 사용했고, 내림차순 정렬을 사용했다. 내림차순 정렬은 sort(begin(), end(), greater<type>()) 형으로 작성한다.

메모리 사용을 줄이고자 처음에 입력받은 카드 레벨들의 벡터에 카드합성 결과를 덮어씌웠다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    cin >> N;
    
    vector<int> meeting(N);
    for(int i = 0; i < N; i++) {
        cin >> meeting[i];
    }
    sort(meeting.begin(), meeting.end(), greater<int>());
    long long gold = 0;
    for(int i = 0; i < N - 1; i++) {
        gold += meeting[i] + meeting[i + 1];
        meeting[i + 1] = max(meeting[i], meeting[i + 1]);
    }
    
    printf("%lld", gold);
}