알고리즘 공부 (2024_10_30)

목표는 하루에 4문제 정도 푸는겁니다!

이렇게 매일 하면 3달이면 240문제, 6달이면 480문제 정도라구요~

평일에만 할꺼긴한데 주말에도 욕심내면 500문제까지 가는게 꿈입니다!

 

 

백준 8980 : 택배

이건 정말 어려웠다. 눈에 안들어 온다 그래야하나. 거진 2시간 넘게 쓴듯.

그리고 결국 스스로의 힘으로 못풀었다는 이야기. 심지어 다른 블로그 많이 봤는데도 이해 못했음 ㅋㅅㅋ

그래도 오래 들여다 보니까 보였는데.

 

우선 많이 운반을 해야 하기 때문에 빨리 내려놓아야 하는게 가장 효율이 좋아졌다.

그렇기 때문에 도착지가 가까운 순서대로 정렬을 했다.

그 다음엔 출발지가 가까운 순서대로 정렬을 진행했다.

 

그렇게 해서 벡터에 담긴 순서대로 데이터를 분석, 기록할 거다.

데이터의 시작 날짜이상, 끝나는 날짜 미만 으로 적재를 하는데, 이때 적재는 트럭에 담을 수 있는 용량 미만이여야 한다. 여기서 말하는 트럭에 담을 수 있는 용량은 이미 실려져 있는 상자와 트럭이 최대 수용 가능한 용량을 고려해야 한다.

 

그래서 DP에는 순서대로 데이터를 기록할때 그 날에 담고있는 상자의 수를 기록하는 식으로 진행한다.

기록할때 마다 해당 데이터를 정답에 추가하면 결과가 도출되는 방식이다.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>

using namespace std;


struct info
{
    int Start;
    int End;
    int Capa;

    bool operator<(const info& other) const
    {
        if (End < other.End)
        {
            return true;
        }
        else if (End == other.End)
        {
            if (Start < other.Start)
            {
                return true;
            }
        }
        return false;
    }
};

int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int N, C, M;
    cin >> N >> C >> M;
    int answer = 0;

    vector<info> MV(M);
    vector<int> DP(100000);
    for (int i = 0; i < M; i++)
    {
        cin >> MV[i].Start >> MV[i].End >> MV[i].Capa;
    }

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

    for (int i = 0; i < M; i++)
    {
        int CanCapa = 0;
        int MaxV = 0;

        for (int j = MV[i].Start; j < MV[i].End; j++)
        {
            MaxV = max(MaxV, DP[j]);
        }

        CanCapa = min(MV[i].Capa, C - MaxV);
        answer += CanCapa;
        for (int j = MV[i].Start; j < MV[i].End; j++)
        {
            DP[j] += CanCapa;
        }
    }
    cout << answer << "\n";
}

 

 

---

 

 

백준 2212 : 센서

이건 문제보고 이게 뭐지...하고 들여다 보다가 번쩍한 문제.

사실 문제가 어렵더라. 이해하기.

거리가 가장 먼 값들을 제외하고 풀어주면 끝

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>

using namespace std;


int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int answer = 0;
    int N, K;
    cin >> N >> K;

    vector<int> NV(N);
    for (int i = 0; i < N; i++)
    {
        cin >> NV[i];
    }
    sort(NV.begin(), NV.end());

    vector<int> DP(N - 1);
    for (int i = 0; i < N - 1; i++)
    {
        DP[i] = NV[i + 1] - NV[i];
    }
    sort(DP.begin(), DP.end(), greater<int>());

    for (int i = K - 1; i < N - 1; i++)
    {
        answer += DP[i];
    }

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

 

 

---

 

 

백준 1459 : 걷기

대각선이 가능한 부분과 직선부분으로 나눠서 해결했다.

대각선이 가능한 부분에선 대각선값과 직선값중 더 낮은 수를 이용하고,

직선 부분에서 홀수면 -1 을 진행하고 직선값을 하나 미리 더해두었다.

 

직선 부분에서도 대각선과 직선을 비교해서 더 낮은 수를 더했다.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>

using namespace std;


int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int X,Y, W,S;
    cin >> X >> Y >> W >> S;
    long long answer = 0;

    long long CanCrossN = min(X, Y);
    answer += CanCrossN * min(2 * W , S);

    long long leftLoad = max(X, Y) - CanCrossN;
    if (leftLoad % 2 == 1)
    {
        answer += W;
        leftLoad -= 1;
    }
    
    answer += min(leftLoad * W , leftLoad * S);

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

 

 

---

 

 

백준 1826 : 연료 채우기

남아있는 기름과 트럭의 위치좌표를 통일했다. 어차피 그만큼 갈 수 있으니까.

그리고 멈춘 곳에서 기름을 채우기로 했다. 어차피 어디서 채웠는지는 카운트 안하니까.

 

우선순위 큐에다가 트럭의 좌표보다 낮은 좌표들을 넣고, 하나씩 꺼내서 채웠다.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int answer = 0;

    int N, L, P;
    cin >> N;

    vector<pair<int, int>> NV(N);
    for (int i = 0; i < N; i++)
    {
        cin >> NV[i].first >> NV[i].second;
    }
    cin >> L >> P;

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

    int CurPoint = P;
    int VPoint = 0;
    priority_queue<int> q;

    while (CurPoint < L)
    {
        while (true)
        {
            if (VPoint >= NV.size())
            {
                break;
            }
            else if (NV[VPoint].first <= CurPoint)
            {
                q.push(NV[VPoint].second);
                VPoint++;
            }
            else
            {
                break;
            }
        }

        if (q.empty())
        {
            answer = -1;
            break;
        }
        else
        {
            CurPoint += q.top();
            q.pop();
            answer++;
        }
    }

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