BOJ 1744 수 묶기 / BOJ 1080 행렬 / BOJ 11000 강의실 배정 (그리디)

백준 BOJ 1744번 : 수 묶기

N개의 수가 주어졌을 때 두 개의 수를 선택하여 곱으로 만들거나, 아니면 그냥 더해서 그 계산식의 결과의 최댓값을 구하는 문제입니다. (이 때 선택하는 두 수는 순서에 관계없이 선택할 수 있습니다.)

 

간단히만 생각하면 큰 양수끼리 곱하고, 절댓값이 큰 두 음수끼리 곱해서 큰 양수를 만드는 정도의 그리디적인 풀이를 떠올릴 수 있습니다.

그러나 몇 가지 예외를 생각해야 하는데 다음과 같습니다.

 

(1) 음수가 홀수개인 경우 : 0이 존재한다면 0과 곱해서 0으로 만들 수 있고, 그렇지 않은 경우 그냥 합에 더해주어야 합니다.

(2) 양수가 홀수개인 경우 : 그냥 더해주면 됩니다.

(3) 1이 존재하는 경우 : x > 0인 x에 대해 x * 1보다 x + 1이 결과값이 더 크므로, 1은 그냥 더해주어야 합니다.

 

우선순위 큐를 두 개 구현하여 음수는 내림차순으로, 양수는 오름차순으로 구현하여 절댓값이 작은 것을 바로 pop하여 사용할 수 있도록 코드를 작성하였습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    int ans = 0, zero = 0;
    priority_queue<int, vector<int>, greater<int>> pos;
    priority_queue<int> neg;

    while(N--) {
        int value; cin >> value;

        if(value == 1) ans += 1;
        else if(value > 0) pos.push(value);
        else if(value < 0) neg.push(value);
        else zero++;
    }

    if(pos.size() % 2 == 1) {
        ans += pos.top();
        pos.pop();
    }

    while(!pos.empty()) {
        int val1 = pos.top();
        pos.pop();

        int val2 = pos.top();
        pos.pop();

        ans += val1 * val2;
    }

    if(neg.size () % 2 == 1) {
        if(zero > 0) neg.pop();
        else {
            ans += neg.top();
            neg.pop();
        }
    }

    while(!neg.empty()) {
        int val1 = neg.top();
        neg.pop();

        int val2 = neg.top();
        neg.pop();

        ans += val1 * val2;
    }

    cout << ans;
}

 

 

백준 BOJ 1080번 : 행렬

크기가 같고 원소가 1과 0으로만 이루어진 두 행렬이 있을 때, 한 행렬에 특정 좌표를 선택하면 3x3 크기의 행렬의 값들을 모두 바꾸는 "연산"을 최소 몇 번 거쳐야 서로 같은 행렬로 만들 수 있는지를 구하는 문제입니다.

 

조금 생각해보면 어떤 좌표를 선택하고 그 좌표를 기준으로 오른쪽 아래로 3x3 행렬을 바꾼다고 할 때, 왼쪽 위에서 오른쪽 아래로 이동하면서 각 좌표에 대해 연산을 선택할지, 또는 하지 않을지에 대한 두 가지 선택지밖에 없으므로 왼쪽 위에서부터 오른쪽 아래로 내려가면서 해당 좌표의 원소가 다르다면 어쩔 수 없이 연산을 해야하고, 그렇지 않으면 하지 않는 경우밖에 없습니다.

 

따라서 이중 for문으로 모든 칸을 검사하면서 원소 값이 다르면 연산을 수행해주기만 하면 됩니다.

만약 모든 칸을 검사하며 연산을 수행했는데도 여전히 원소의 값이 다른 경우가 존재한다면 그 경우에는 행렬을 같게 만들 수 없는 것이므로 -1을 출력해주고, 그렇지 않은 경우는 그냥 cnt 값을 출력해주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;
    cin.ignore();

    char a[51][51], b[51][51];

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) cin >> a[i][j];
        cin.ignore();
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) cin >> b[i][j];
        cin.ignore();
    }

    int cnt = 0;
    for(int i=0; i<N-2; i++)
        for(int j=0; j<M-2; j++)
            if(a[i][j] != b[i][j]) {
                cnt++;
                for(int k=0; k<3; k++)
                    for(int l=0; l<3; l++) {
                        if(a[i+k][j+l] == '0') a[i+k][j+l] = '1';
                        else a[i+k][j+l] = '0';
                    }
            }

    bool check = true;
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
            if(a[i][j] != b[i][j]) check = false;

    if(!check) cout << "-1";
    else cout << cnt;
}

 

 

백준 BOJ 11000번 : 강의실 배정

N개의 강의의 시작하는 시간과 끝나는 시간이 주어질 때, 모든 강의를 하기 위해서는 강의실이 최소 몇 개 필요한지를 구하는 문제입니다. (즉, 시간이 겹치는 강의가 최대 몇 개 있냐를 구해주면 됨)

 

이런 문제의 경우에는 다양한 풀이가 있을 수 있겠지만, 우선순위 큐를 활용하여 다음과 같이 간단하게 풀이할 수 있는 방법이 있습니다.

먼저 시작 시간을 기준으로 오름차순으로 강의들을 정렬해줍니다.

 

그 다음 우선순위 큐에 끝나는 시간을 넣고, 시작하는 강의 순서대로 비교하면서 만약 시작하는 시간이 우선순위 큐의 top에 있는 강의의 끝나는 시간보다 앞선다면, 그 강의는 큐에 있는 모든 강의들과 시간이 겹친다는 의미이므로 우선순위 큐에 끝나는 시간을 추가해주면 됩니다.

반대로 강의의 시작 시간이 우선순위 큐의 top에 있는 강의의 끝나는 시간과 같거나 더 늦다면, 그 강의와는 겹치지 않으므로 해당 강의를 pop 해주고 방금 비교한 강의의 끝나는 시간을 넣어주면 됩니다.

 

+ 물론 top이 아닌 다른 강의와도 시간이 겹치지 않을 수 있지만, 이 풀이는 특정 시점에서 시간이 겹치는 강의 수의 최댓값만 구해주면 되기 때문에 굳이 그 이상으로 pop을 하지 않고, 마지막에 큐에 들어있는 데이터의 수를 답으로 얻어내는 방식으로 해결하는 풀이입니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<pair<int, int>> time(N);
    for(int i=0; i<N; i++)
        cin >> time[i].first >> time[i].second;

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

    priority_queue<int, vector<int>, greater<int>> pQueue;
    pQueue.push(time[0].second);

    for(int i=1; i<N; i++) {
        if(time[i].first < pQueue.top())
            pQueue.push(time[i].second);
        else {
            pQueue.pop();
            pQueue.push(time[i].second);
        }
    }

    cout << pQueue.size();
}