알고리즘 공부 (2024_11_8)

 

백준 1114 : 통나무 자르기

딱 보고 이분탐색이구나 했는데 눈에 안들어오더라... 왜캐 어렵지...알겠는데 모르겠다.

그래서 결국 블로그 찾아 댕겨서 풀었다.

 

https://hojun.tistory.com/9

[백준] 1114번 - 통나무 자르기

 

 

---

 

 

백준 2012 : 등수 매기기

불만도만 측정하면 되는 문제여서 뭐 손해를 가장 덜 보는 순으로 고려했다.

그러면 참가자 다 우선순위 큐에 넣고 순서대로 빼서 계산했다.

#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 N;
    priority_queue<int, vector<int>, greater<int>> q;
    long long answer = 0;
    int count = 1;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int k;
        cin >> k;
        q.push(k);
    }

    while (!q.empty())
    {
        int cur = q.top();
        q.pop();

        answer += abs(cur - count);
        count ++;
    }

    cout << answer;
}

 

 

---

 

 

백준 4716 : 풍선

이것도 예전에 풀었던 트럭문제랑 비슷하더라. 손해를 가장 많이 보는곳 기준으로 우선순위 내려서 풀었다.

손해가 가장 심한 곳부터 고려해서 문제를 해결했다.

문제 입력에 계속 반복하다가 0 0 0 나오면 종료라길래 while 문을 추가했다.

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

using namespace std;

struct info
{
    int K, Da, Db;

    info(int k, int da, int db) : K(k), Da(da), Db(db) {};
    const bool operator<(const info& other) const
    {
        return abs(Da - Db) < abs(other.Da - other.Db);
    }
};

int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    while (true)
    {
        int N, A, B;
        int answer = 0;

        priority_queue<info> q;
        cin >> N >> A >> B;
        if (N == 0 && A == 0 && B == 0)
        {
            break;
        }

        for (int i = 0; i < N; i++)
        {
            int K, Da, Db;
            cin >> K >> Da >> Db;

            q.push(info(K, Da, Db));
        }

        while (!q.empty())
        {
            info cur = q.top();
            q.pop();

            if (cur.Da < cur.Db)
            {
                int useA = min(cur.K, A);
                answer += useA * cur.Da;
                A -= useA;

                int useB = cur.K - useA;
                answer += useB * cur.Db;
                B -= useB;
            }
            else 
            {
                int useB = min(cur.K, B);
                answer += useB * cur.Db;
                B -= useB;

                int useA = cur.K - useB;
                answer += useA * cur.Da;
                A -= useA;
            }
        }
        cout << answer << "\n";
    }

}

 

 

---

 

 

백준 1543 : 문서 검색

그냥 글자 찾으면 다 검색하도록 했다.

근데 T가 더 길수도 있다는 오류에 빠져서 시간을 좀 썼었다.

조건에 보면 T가 더 짧다는 조건이 없더라. 그래서 T가 더 길수도 있기 때문에 예외처리를 걸어야 하더라.

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

using namespace std;

int main() {
    string S, T;
    int answer = 0;

    getline(cin, S);
    getline(cin, T);

    if (S.size() < T.size()) 
    {
        cout << answer;
        return 0;
    }

    for (int point = 0; point <= S.size() - T.size(); point++)
    {
        if (S[point] == T[0])
        {
            int i = 0;
            for (i = 0; i < T.size(); i++)
            {
                if (S[point + i] != T[i])
                {
                    break;
                }
            }

            if (i == T.size())
            {
                answer++;
                point += T.size() - 1;
            }
        }
    }

    cout << answer;
}