알고리즘 스터디 50일차

1. 강의실 배정

1) 문제

문제 설명
수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력
강의실의 개수를 출력하라.

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

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

int N;

bool cmp(const vector<int>& a, const vector<int>& b)
{
    return a[1] < b[1];
}

// 빨리 끝나는 강의부터 일단 강의실을 주자.
int main()
{
    cin >> N;
    vector<int> startTime(N);
    vector<int> endTime(N); 

    for (int i=0; i<N; i++)
    {
        int start;
        int end;
        cin >> startTime[i] >> endTime[i];
    }

    sort(startTime.begin(), startTime.end());
    sort(endTime.begin(), endTime.end());

    int startIndex = 0, endIndex = 0;
    int usedRoomCnt = 0, answer = 0;

    while(startIndex < N)
    {
        // 현재 상황에서
        // 가장 빨리 시작하는 시간이 가장 빨리 끝나는 것보다 작으면
        // ( startIndex번째 강의는 아직 진행중 )
        if (startTime[startIndex] < endTime[endIndex])
        {
            // 사용중인 강의실 수(동시 진행 중인 강의 수) 증가
            usedRoomCnt++;
            // 값 갱신
            answer = max(answer, usedRoomCnt);
            // 다음 시작 시간에 대해서 확인
            startIndex++;
        }
        // 시작 시간이 가장 빨리 끝나는 시간 이후
        // 겹치지 않음
        else 
        {
            // 사용중인 강의실 수 감소
            usedRoomCnt--;
            // 다음 종료 시간에 대해서 확인
            endIndex++;
        }
    }

    cout << answer << '\n';

    return 0;
}

2. 멀티탭 스케쥴링

1) 문제

문제 설명
시플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

입력
첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.

출력
하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;

int N, K;
unordered_map<int, queue<int>> timeMap;
struct Cmp
{
    bool operator()(const int& a, const int& b)
    {
        // a가 더이상 나오지 않는 경우 a를 먼저
        if (timeMap[a].size() == 0 && timeMap[b].size() != 0) return false;
        // b가 더이상 나오지 않는 경우 b를 먼저
        if (timeMap[a].size() != 0 && timeMap[b].size() == 0) return true;
        // 둘다 나오지 않는 경우 상관없음
        if (timeMap[a].size() == 0 && timeMap[b].size() == 0) return false;
        // 둘 중 더 늦게 나오는데 앞으로
        // true면 b가 우선
        return (timeMap[a].front() < timeMap[b].front());
    }
};

// 가장 늦게 나오는걸 먼저 뽑자!
int main()
{
    cin >> N >> K;

    vector<int> cntVec (K+1);
    vector<int> seq;
    unordered_set<int> plugged;

    for (int i=1; i<=K; i++)
    {
        int name;
        cin >> name;
        timeMap[name].push(i-1);
        seq.push_back(name);
    }

    int cnt = 0;
    for (int i=0; i<seq.size(); i++)
    {
        // 현재 시점 삭제
        timeMap[seq[i]].pop();

        // 이미 있는거면 넘어감
        if (plugged.find(seq[i]) != plugged.end()) continue;

        // 꽉 찬 경우
        if (plugged.size() == N)
        {
            // 지금 이후로 가장 늦게 등장하는 걸 뽑음
            priority_queue<int, vector<int> , Cmp>pq (plugged.begin(), plugged.end());
            int top = pq.top();
            plugged.erase(top);
            cnt++;
        }

        // seq[i] 기기 플러그 꼽기
        plugged.insert(seq[i]);

    }

    cout << cnt << '\n';

    return 0;
}

3. 단어 수학

1) 문제

문제 설명
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <cmath>
using namespace std;

int N;
vector<string> strVec;
unordered_map<char, int> C2Itable;
unordered_map<char, long long> posWeight;
set<char> alphabet;
// 알파벳중 기댓값이 가장 큰 친구에게 큰 값을 주자
int main()
{
    cin >> N;
    int maxLen = 0;
    for (int i=0; i<N; i++)
    {
        string str;
        cin >> str;
        strVec.push_back(str);

        int len = strVec[i].size();
        long long weight = 1;
        for (int j = 0; j < len; j++) 
        {
            posWeight[strVec[i][j]] += static_cast<long long>(pow(10, len - j - 1));
        }
    }

    set<char> alphabet;
    for (auto& p : posWeight) 
    {
        alphabet.insert(p.first);
    }

    vector<bool> numVisited(10);
    vector<char> sortedvec(alphabet.begin(), alphabet.end());
    sort(sortedvec.begin(), sortedvec.end(), [&](const char& a, const char& b) {
        return posWeight[a] > posWeight[b];
    });

    for (auto& a : sortedvec) 
    {
        for (int num = 9; num >= 0; num--) 
        {
            if (!numVisited[num]) 
            {
                numVisited[num] = true;
                C2Itable[a] = num;
                break;
            }
        }
    }

    long long answer = 0;
    for (auto &s : strVec) 
    {
        int len = s.size();
        for (int j = 0; j < len; j++) 
        {
            answer += C2Itable[s[j]] * static_cast<long long>(pow(10, len - j - 1));
        }
    }

    cout << answer << "\n";
    return 0;
}

4. 센서

1) 문제

문제 설명
고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력
첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

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

int N;
int K;

// 거리가 짧은거 끼리 묶자
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    cin >> K;
    vector<int> vec;
    set<int> s;
    for (int i=0; i<N; i++)
    {
        int temp;
        cin >> temp;
        s.insert(temp);
    }

    vec = vector<int>(s.begin(), s.end());
    vector<int> rightDist;

    // 자신의 오른쪽에 있는 센서와의 거리 (연결)
    for (int i=0; i<vec.size()-1; i++)
    {
        rightDist.push_back(vec[i+1] - vec[i]);
    }

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

    // 원형이 아닌 무언가를 k 개의 그룹으로 나누려면
    // k-1번 조합을 끊으면 된다.
    // 직사각형을 3개의 직사각형으로 나누려면? -> 2번 잘라야함
    // 연결을 K-1번 끊기
    for (int i=0; i<K-1; i++)
    {
        if (rightDist.size() == 0)
            break;
        rightDist.pop_back();
    }

    int answer = 0;
    // 남아있는 연결의 값을 더하기
    if (rightDist.size() != 0)
        answer = accumulate(rightDist.begin(), rightDist.end(), 0);
    cout << answer << '\n';
    return 0;
}

5. 회의실 배정

1) 문제

문제 설명
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

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

int N;

// 가장 빨리 끝나는 회의를 먼저 고른다.
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int cnt = 0, ans = 1;

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

    sort(timeVec.begin(), timeVec.end(), 
    [](const pair<int, int>& a, const pair<int, int>&b)
    {
        if (a.second == b.second)
            return a.first < b.first;
        return a.second < b.second;
    });

    int frontEndTime = timeVec[0].second; 

    for (int i=1; i<N; i++)
    {
        if (frontEndTime > timeVec[i].first && frontEndTime <= timeVec[i].second) continue;

        ans++;
        frontEndTime = timeVec[i].second;
    }

    cout << ans;
    return 0;
}

6. 저울

1) 문제

문제 설명
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.
입력
첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력
첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

$[0,X]$ 까지의 수를 표현 할 수 있으면
$[a[i],X+a[i]]$ 까지 표현할 수 있음
위 두개의 범위가 처음으로 겹치지 않는 곳을 찾는 문제

2) 풀이

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

int N;

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

    cin >> N;

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

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

    int ans = 0;
    for (auto& v : vec)
    {
        if (ans + 1 < v)
            break;
        ans += v;
    }

    cout << ans+1 << '\n';

    return 0;
}