99코딩

• 기지국 하나가 커버하는 영역이 W = w x 2 + 1, 전달되지 않는 영역의 크기가 A일 때 
• A % W == 0이면 필요한 기지국의 최소 개수는 A / W, 아니라면 A / W + 1이 됨

• 그림에서 처럼 6,7,8,9 총 4의 크기의 영역이 있고 기지국의 범위가 3이면 4 / 3 + 1 = 2가 됨
• 만약 6, 7, 8 이라면 A / W + 1을 사용하면 3 / 3 + 1 = 2가 되버림
• > A % W == 0이라면 A / W + 1에서 1을 빼줄 필요가 있음

위 공식을 통해 모든 영역 커버를 위한 기지국 설치의 최소 개수를 구하면 되지만 아래 2가지를 추가로 고려해야함

• 첫 번째 기지국이 1번 아파트까지 커버하지 못할 때
• 마지막 기지국이 n번 아파트까지 커버하지 못할 때

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

// n = 아파트 개수, stations = 기지국이 설치된 아파트 번호 배열(오름차순 정렬), w = 전파 도달 거리
// 전파가 전달되지 않는 영역에서 모든 영역이 전파를 전달 받으려면 최소 몇 개의 기지국을 설치해야하는가?
// 기지국 하나가 커버할 수 있는 영역은 w x 2 + 1, 이하 W
// 전달되지 않는 영역 하나의 크기를 A라고 할 때 해당 영역을 커버하기 위한 기지국의 최소 개수는
// A / W + 1이 된다. 단, A % W == 0이면 A / W가 된다.
// ex) 커버할 수 있는 영역이 3이고 전달되지 않는 영역 하나의 크기가 3이면 기지국은 하나 필요 => 3 / 3 == 1

int calcStation(int start, int end, int W) {
    int area = end - start + 1;
    
    // 두 기지국이 커버하는 영역이 겹칠 때
    if(area <= 0) return 0;
    // A % W == 0일 때
    else if(area % W == 0) return area / W;
    else return area / W + 1;
}

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int W = w * 2 + 1;
    
    for(int i = 0; i < stations.size(); i++) {
        // 첫 번째 아파트일 때
        if(!i) {
            // 1번 아파트까지 커버한다면 패스
            if((stations[i] - w) == 0) continue;
            // 1번 아파트까지 커버하지 못한다면
            else answer += calcStation(1, stations[i] - w - 1, W);
        }
        else {
            // 영역 계산
            answer += calcStation(stations[i - 1] + w + 1, stations[i] - w - 1, W);
        }
    }
    
    // 마지막 기지국이 n번 아파트까지 커버하지 못할 때
    if(stations[stations.size() - 1] + w < n)
        answer += calcStation(stations[stations.size() - 1] + w + 1, n, W);
    
    return answer;
}

• 핵심은 정렬과 b < a이면 B 안에서 b보다 상대적으로 작은 숫자를 사용해야하는 것
• 전자는 sort를 사용했고 후자는 정렬된 배열에서 A 기준으로 역방향으로 순회하며 b < a면 idxB의 값을 감소시키지 않는 것으로 해결

#include <string>
#include <vector>
#include <algorithm>

// 두 팀의 순서가 모두 고정된 것이 아니므로 순서는 무시
// 두 배열 모두 정렬한 뒤에 size - 1부터 비교하면 될 듯
// 이렇게하면 a보다 더 큰 숫자 중에 제일 작은 숫자를 뽑거나 할 필요는 없을듯
// b가 a보다 작으면 B 안에서 b보다 상대적으로 작은 숫자를 꺼내야함
// 두 개 배열을 두고 size - 1부터 --해가면서 A가 0에 도달하면 반복을 끝내면 될거 같음

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    
    int idxA = A.size() - 1;
    int idxB = idxA;
    
    // 정렬
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    
    for(int i = idxA; idxA >= 0; i--) {
        int numA = A[idxA];
        int numB = B[idxB];
        
        // numB가 numA보다 크면
        if(numB > numA) {
            // answer++하고 B에서 다음으로 큰 숫자를 준비
            answer++;
            idxB--;
        }
        
        // A에서 다음으로 큰 숫자 준비
        idxA--;
    }
    
    return answer;
}

• 일단 정렬
• 첫 번째 차량을 기준으로 해당 차량의 진입 지점보다 멀고 진출 지점보다 가까운 차량을 찾음
• 진입 지점이 진출 지점보다 멀다면 현재 카메라로는 관측이 불가능하므로 answer를 증가시키고
• 진입 지점과 진출 지점을 갱신
• 진입 지점과 진출 지점이 같은 경우에는 갱신 X
• 진출 지점이 가깝다면 해당 지점에 대한 값을 갱신
• 마지막에 무조건 한 대 또는 한 집합이 남으므로 answer = 1로 해주고 시작
• 이를 반복

2레벨에 디펜스 게임?이랑 비슷한 느낌으로 접근하면 됨

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 일단 정렬
// 첫 번째 차량을 기준으로 해당 차량의 진입 지점보다 멀고 진출 지점보다 가까운 차량을 찾음
// 진입 지점이 진출 지점보다 멀다면 현재 카메라로는 관측이 불가능하므로 answer를 증가시키고
// 진입 지점과 진출 지점을 갱신
// 진입 지점과 진출 지점이 같은 경우에는 갱신 X
// 진출 지점이 가깝다면 해당 지점에 대한 값을 갱신
// 마지막에 무조건 한 대 또는 한 집합이 남으므로 answer = 1로 해주고 시작
// 이를 반복

int solution(vector<vector<int>> routes) {
    int answer = 1;
    
    sort(routes.begin(), routes.end());
    
    int enter = routes[0][0];
    int exit = routes[0][1];
    
    for(int i = 1; i < routes.size(); i++) {
        if(routes[i][0] > exit) {
            enter = routes[i][0];
            exit = routes[i][1];
            answer++;
        }
        
        if(routes[i][0] == exit)
            continue;
        
        if(routes[i][1] < exit)
            exit = routes[i][1];
    }
    
    return answer;
}

• 집합 내의 숫자들 간의 격차가 적을수록 곱이 최대가 됨
• s를 n으로 나눈 몫이 자연수가 아니면(= s가 n보다 작으면) 합이 s인 집합을 만들 수 없으므로 -1 리턴
• 자연수면 나눈 몫을 n개 저장하고 나머지만큼 각 원소에 1씩 더해줌
• 오름차순 정렬 수행

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 집합 내의 숫자들 간의 격차가 적을수록 곱이 최대가 됨
// s를 n으로 나눈 몫이 자연수가 아니면(= s가 n보다 작으면) 합이 s인 집합을 만들 수 없으므로 -1 리턴
// 자연수면 나눈 몫을 n개 저장하고 나머지만큼 각 원소에 1씩 더해줌
// 오름차순 정렬 수행

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    if(n > s) return {-1};
    
    int a = s / n;
    int b = s % n;
    
    for(int i = 0; i < n; i++)
        answer.push_back(a);
    
    for(int i = 0; i < b; i++)
        answer[i]++;
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

• 오른쪽과 아래쪽으로만 이동 가능
• 각 격자마다 해당 격자까지 도달할 수 있는 경로의 수를 저장
• [i][j]에 도달할 수 있는 경로의 수를 점화식으로 나타내면 dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 물에 잠긴 곳은 -1로 저장한 뒤 방문 시 0으로 바꿈

위 조건을 그림으로 나타내면 아래처럼 됨

#include <string>
#include <vector>

using namespace std;

// dp 문제
// 각 격자마다 해당 격자까지 도달할 수 있는 경로 개수를 저장
// 오른쪽과 아래쪽으로만 이동 가능
// 위 조건에 따라 dp[i][j]에 도달할 수 있는 경로의 수는 dp[i-1][j] + dp[i][j-1]
// 물에 잠긴 곳은 -1으로

int dp[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    dp[1][1] = 1;
    
    for(int i = 0; i < puddles.size(); i++)
        dp[puddles[i][1]][puddles[i][0]] = -1;
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            // 시작점일 때
            if((i == 1 && j == 1)) continue;
            
            // 물에 잠긴 곳일 때
            if(dp[i][j] == -1) {
                dp[i][j] = 0;
                continue;
            }
            
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
        }
    }
    
    return dp[n][m];
}

• 야근지수가 최소가 되려면 작업량을 줄이면서 해당 작업량들간의 차이가 최소가 되어야함
• 작업량을 내림차순으로 정렬한 뒤에 높은 값을 -1씩 해주는걸 반복
• > 우선순위 큐에 작업량을 삽입하고 top을 꺼내서 -1 해주고 다시 삽입을 반복

#include <string>
#include <vector>
#include <queue>

using namespace std;

// works의 시간을 줄이면서 works의 작업량들의 값이 비슷해야함
// 예를 들어 [4,3,3]에서 n = 4일 때 [0,3,3]이 되면 작업 하나는 마쳤지만 야근 지수는 제곱을 해서 0 + 9 + 9 = 18이 됨
// 하지만 [2,2,2]가 되면 4 + 4 + 4 = 12로 최소가 됨
// 우선순위 큐로 제일 많이 남은 작업량을 꺼내서 -1 해주고 다시 담는 걸 n번 반복

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> pq;
    
    for(int i = 0; i < works.size(); i++)
        pq.push(works[i]);
    
    for(int i = 0; i < n; i++) {
        if(pq.empty()) break;
        
        int num = pq.top() - 1;
        pq.pop();
        
        if(num == 0) continue;
        else pq.push(num);
    }
    
    if(pq.empty())
        return 0;
    
    for(int i = 0; !pq.empty(); i++) {
        int num = pq.top();
        answer += num * num ;
        pq.pop();
    }
    
    return answer;
}

• 3레벨에서 의외로 기초적인 dfs/bfs 문제
• 그래도 변수명을 제대로 썼는지 확인하자, 다음 노드로 갱신해야하는데 현재 노드로 갱신하고 있는걸 코드 실행 해보고 알았다...

#include <string>
#include <vector>
#include <queue>

using namespace std;

bool isVisited[200] = {false};
int answer = 0;
queue<int> q;

void bfs(int startNode, int n, vector<vector<int>> computers) {
    q.push(startNode);
    isVisited[startNode] = true;
    
    while(!q.empty()) {
        int curNode = q.front();
        q.pop();
        isVisited[nextNode] = true;
        
        for(int nextNode = 0; nextNode < n; nextNode++) {
            if(computers[curNode][nextNode] == 1 && !isVisited[nextNode]) {
                q.push(nextNode);
                
            }
        }
    }
    
    answer++;
}

int solution(int n, vector<vector<int>> computers) {    
    for(int i = 0; i < n; i++) {
        if(!isVisited[i]) {
            bfs(i, n, computers);
        }
    }
    
    return answer;
}

• 각각 내림차순, 오름차순으로 값을 저장하는 우선순위 큐 2개를 활용
• 삽입은 두 큐에 동시에 수행하고 최댓값 삭제는 내림차순 큐에서 최솟값 삭제는 오름차순 큐에서 수행
• 추가로 삽입을 수행한 횟수와 삭제를 수행한 횟수가 같아지면 두 큐를 모두 비워줘야함 

#include <string>
#include <vector>
#include <sstream>
#include <queue>

using namespace std;

// 우선순위큐 2개를 생성해서 하나는 내림차순, 하나는 오름차순으로 정렬
// 삽입 같은 경우에는 두 큐에 모두 수행
// 최댓값은 내림차순, 최솟값은 오름차순 큐에서 수행
// 이후 하나가 비어있으면 나머지 하나도 비어있는 것이므로 [0, 0] 리턴
// 아니라면 각각 front() 값을 리턴하면 됨

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int> lesser_pq;
    priority_queue<int, vector<int>, greater<int>> greater_pq;
    int cnt = 0;
    
    for(int i = 0; i < operations.size(); i++) {
        if(operations[i] == "D 1") {
            if(!lesser_pq.empty()) {
                lesser_pq.pop();
                cnt--;
            }
        }
        else if(operations[i] == "D -1") {
            if(!greater_pq.empty()) {
                greater_pq.pop();
                cnt--;
            }
        }
        else {
            string str = "";
            istringstream iss(operations[i]);
            
            iss >> str >> str;
            
            lesser_pq.push(stoi(str));
            greater_pq.push(stoi(str));
            
            cnt++;
        }
        
        if(cnt == 0) {
            while(!lesser_pq.empty()) lesser_pq.pop();
            while(!greater_pq.empty()) greater_pq.pop();
        }
    }
    
    if(lesser_pq.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(lesser_pq.top());
        answer.push_back(greater_pq.top());
    }
    
    return answer;
}