알고리즘 공부 (2024_10_31)

 

오케이 오늘도 레츠고

 

 

백준 5585 : 거스름 돈

거스름돈 하면 냅색 알고리즘 생각나서 그렇게 하려다가 거스름돈 수가 무한이라길래.

그리고 금액도 정해져 있길래. 거스름 돈 액수도 정해져 있길래 그냥 하나씩 했다.

 

#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;
    cin >> N;

    int Charge = 1000 - N;

    answer += Charge / 500;
    Charge = Charge % 500;

    answer += Charge / 100;
    Charge = Charge % 100;

    answer += Charge / 50;
    Charge = Charge % 50;

    answer += Charge / 10;
    Charge = Charge % 10;

    answer += Charge / 5;
    Charge = Charge % 5;

    answer += Charge / 1;

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

 

 

---

 

 

백준 1508 : 레이스

이분탐색으로 문제를 풀었는데, N까지의 절반을 기준으로 성공하면 늘리고 실패하면 줄이는 방식으로 길이를 서칭해 나아갔다.

 

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

using namespace std;



int N, M, K;
int inp[500];

int l, r, mid, pos;
int cnt, bef, dist;
vector< int > ans;

int main() {

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

    int N, M, K;

    cin >> N >> M >> K;

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

    vector<int> answer(K);
    int LP = 0;
    int RP = N;

    while (LP <= RP)
    {
        int mid = (LP + RP) / 2;
        vector<int> res(K, -1);

        res[0] = 1;
        int check = 1;
        int prev = 0;

        for (int i = 1; i < K; i++)
        {
            if (KV[i] - KV[prev] >= mid)
            {
                res[i] = 1;
                prev = i;
                check++;
                if (M == check)
                {
                    break;
                }
            }
            else
            {
                res[i] = 0;
            }
        }

        for (int i = 0; i < K; i++)
        {
            if (res[i] == -1)
            {
                res[i] = 0;
            }
        }

        if(check == M)
        {
            LP = mid + 1;
            answer = res;
        }
        else
        {
            RP = mid - 1;
        }

    }

    for (int i = 0; i < K; i++)
    {
        cout << answer[i];
    }
}

 

 

---

 

 

백준 1802 : 종이접기

이거는 진짜 눈에 안보여서 옆에 있던 종이 막 접어가며 풀었던 문제.

사실은 규칙이 안보여서.

 

그러다가 갑자기 눈에 들어오더라. 접히는 부분을 기준으로 양 옆부분이 다시 접힌다는게 보였다.

그리고 결과는 항상 둘이 반대로 나온다는 것도.

정말 우연히 문제를 푼듯.

 

처음엔 재귀로 안풀었는데 반례를 찾아서 재귀로 풀었다.

원래는 중심 기준으로 한번만 진행했는데 0000111 이라면 안되는 거여서 재귀로 다시 풀었다.

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

using namespace std;

string Target;

bool UPDown(int LP, int RP, int Count)
{
    if (LP == RP)
    {
        return true;
    }

    for (int i = 0; i < Count; i++)
    {
        if (Target[LP] == Target[RP])
        {
            return false;
        }
        else
        {
            LP++;
            RP--;
        }
    }

    return UPDown(0, Count - 1, Count / 2);
}

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

    int T;
    cin >> T;

    for (int i = 0; i < T; i++)
    {
        cin >> Target;
        if (UPDown(0, Target.size() - 1, Target.size() / 2))
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
}

 

 

---

 

 

백준 1294 : 문자열 장식

문제 보자마자 LIS다 하고 댐볐다가 풀면 풀수록 이상한데 싶었던 문제.

처음 풀이는 struct에 데이터를 구현하려고 했다. 문자, 문자의 번째, 그리고 LIS에 기록될 수 이렇게 해서 vector를 나열하고 sort로 정렬하려고 했는데,

 

하다 보니까 이럴거면 그냥 글자 하나씩 적는게 낫겠는데 싶더라.

최대가 20000개의 글자밖에 안되는 조건이여서 이정도면 그냥 하나씩 하는게 낫겠다 싶어서 갑자기 방향을 틀었던 문제다.

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

using namespace std;

struct GreaterString
{
    bool operator() (const string& s1, const string& s2) const
    {
        return (s1 + s2 > s2 + s1);
    }
};

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

    int N;
    cin >> N;
    string answer = "";

    priority_queue<string, vector<string>, GreaterString> q;

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

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

        answer += cur[0];
        if (cur.length() > 1)
        {
            q.push(cur.substr(1, cur.length() - 1));
        }
    }

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