알고리즘 공부 (2024_10_29)

알고리즘 문제 풀기 시작. 오늘부터야.

 

목표는 하루에 4문제씩 풀기

너무 막 어렵지 않은걸로 다가.

 

 

백준 3109 : 빵집

왼쪽에서 오른쪽으로 길찾기 알고리즘이고, 최대 몇가닥이나 갈 수 있는지 물어보는 문제.

당연히 DFS로 풀었다.

 

나는 타임오버가 계속 나길래 뭐지 하고 오래 들여다 봤었는데 백트래킹이 문제더라.

어차피 안되는 경로는 다시 활성화 하면 안되는 문제였다.

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

using namespace std;

int dx[3] = {1, 1, 1};
int dy[3] = {-1, 0, 1};

int R = 0;
int C = 0;

vector<vector<int>> curMap;

bool DFS(int curY, int curX)
{
    if (curX == C)
    {
        return true;
    }
    else
    {
        curMap[curY][curX] = 1;
        for (int i = 0; i < 3; i++)
        {
            int nextY = dy[i] + curY;
            int nextX = dx[i] + curX;

            if (nextX >= 1 && nextX <= C && nextY >= 1 && nextY <= R && curMap[nextY][nextX] != 1)
            {
                if (DFS(nextY, nextX))
                {
                    return true;
                }
            }
        }
    }
    return false;
    
}


int main() {

    streambuf* originalCin = cin.rdbuf();
    ifstream inputFile("input.txt");
    if (!inputFile.is_open()) {
        cerr << "파일을 열 수 없습니다." << endl;
        return 1;
    }
    cin.rdbuf(inputFile.rdbuf());

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

    int answer = 0;
    cin >> R >> C;

    curMap.resize(R + 1, vector<int>(C + 1,0));

    for (int i = 1; i < R + 1; i++)
    {
        for (int j = 1; j < C + 1; j++)
        {
            char N;
            cin >> N;

            if (N == 'x')
            {
                curMap[i][j] = 1;
            }
        }
    }

    for (int i = 1; i < R + 1; i++)
    {
        if (DFS(i, 1))
        {
            answer++;
        }
    }

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

 

 

 

---

 

 

 

백준 1781 : 컵라면

작업을 시간내에 끝내고 보상을 받는 DP 알고리즘을 푸는 문제.

그랬는데 나는 이걸 죽어도 틀렸다길래 뭐가 잘못된거야 하고 반례를 찾아서 깨우쳤다.

작업 데드라인이 3일이라면 작업을 1이나 2에서 진행할 수 있더라. 이걸 몰라서 삽질했다.

https://seungbin0619.tistory.com/89

 

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

using namespace std;

int main() {

    streambuf* originalCin = cin.rdbuf();
    ifstream inputFile("input.txt");
    if (!inputFile.is_open()) {
        cerr << "파일을 열 수 없습니다." << endl;
        return 1;
    }
    cin.rdbuf(inputFile.rdbuf());

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

    vector<pair<int, int>> V;

    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;
        V.push_back({a, b});
    }
    sort(V.begin(), V.end());
    priority_queue<int, vector<int>, greater<int>> q;

    for (int i = 0; i < V.size(); i++)
    {
        answer += V[i].second;
        q.push(V[i].second);

        if (V[i].first < q.size())
        {
            answer -= q.top();
            q.pop();
        }
    }
	cout << answer << "\n";
}

 

 

---

 

 

백준 1202 : 보석도둑

 

처음엔 냅색문제인줄 알았는데 보석이 하나밖에 안들어간다길래 그냥 우선순위 큐로 집어넣어봤다.

시간 초과가 나길래 for문으로 하나씩 돌리지말고 while문으로 point를 지정해서 다음번째를 지정해주었더니 해결되었다.

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

using namespace std;

int main() {

    streambuf* originalCin = cin.rdbuf();
    ifstream inputFile("input.txt");
    if (!inputFile.is_open()) {
        cerr << "파일을 열 수 없습니다." << endl;
        return 1;
    }
    cin.rdbuf(inputFile.rdbuf());

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

    cin >> N >> K;
    vector<int> Bag(K);
    vector<pair<int, int>> Jewel(N);

    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;
        Jewel[i] = {a, b};
    }
    for (int i = 0; i < K; i++)
    {
        cin >> Bag[i];
    }

    sort(Bag.begin(), Bag.end());
    sort(Jewel.begin(), Jewel.end());

    priority_queue<int> q;
    int point = 0;

    for (int i = 0; i < K; i++)
    {
        while (point < N && Jewel[point].first <= Bag[i])
        {
            q.push(Jewel[point].second);
            point++;
        }

        if (!q.empty())
        {
            answer += q.top();
            q.pop();
        }
    }

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

 

 

 

---

 

 

백준 1911 : 흙길 보수하기

널빤지를 총 몇개를 깔아야 웅덩이를 피하는지 알아보는 알고리즘인데.

사실 이건 그냥 저번 문제에서 좌표로 풀었기 때문에 좌표쓰면 되겠는데 싶어서 해줬더니 바로 해결됐다.

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

using namespace std;

int main() {

    streambuf* originalCin = cin.rdbuf();
    ifstream inputFile("input.txt");
    if (!inputFile.is_open()) {
        cerr << "파일을 열 수 없습니다." << endl;
        return 1;
    }
    cin.rdbuf(inputFile.rdbuf());

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

    int N;
    int L;

    cin >> N >> L;
    vector<pair<int, int>> V(N);

    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;
        V[i] = {a, b};
    }
    sort(V.begin(), V.end());
    int point = 0;

    for (int i = 0; i < N; i++)
    {
        if (V[i].first > point)
        {
            point = V[i].first;
        }
        while (point < V[i].second)
        {
            point += L;
            answer++;
        }
    }

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