급하게임개발

https://www.acmicpc.net/problem/1744

이 문제의 경우 흐름대로 생각하면 그게 정답이다 단 주의 할점은 단지 하나의 priority queue로 만한다면 음수부분의 처리가 이상하게 될것이다 이에 나는 음수와 0을 저장하는 priority queue와 양수만을 저장해주는 priority queue로 작성하였으며 음수 와 0을 묶은 이유는 음수와 음수의  곱은 양수이고 만약 음수와 0만 큐에 남았을 때는 2개를 곱하여 0을 반환함으로 작은 값을 반환할거라고 생각했다

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
	priority_queue<int> plusNum;
	priority_queue<int,vector<int>, greater<int>> negativeNum;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp1;
		cin >> temp1;
		if (temp1 > 0) {
			plusNum.push(temp1);
		}
		else {
			negativeNum.push(temp1);
		}
	}
	int sum = 0;
	while (!plusNum.empty())
	{
		int num1, num2;
		num1 = plusNum.top();
		plusNum.pop();
		if (plusNum.empty()) {
			sum += num1;
			break;
		}
		num2 = plusNum.top();
		plusNum.pop();

		if (num1 != 1 && num2 != 1) {
			sum += num1 * num2;
		}
		else {
			sum += num1 + num2;
		}
	}
	while (!negativeNum.empty())
	{
		int num1, num2;
		num1 = negativeNum.top();
		negativeNum.pop();
		if (negativeNum.empty()) {
			sum += num1;
			break;
		}
		num2 = negativeNum.top();
		negativeNum.pop();
		sum += num1 * num2;

	}

	cout << sum;

}

https://www.acmicpc.net/problem/13904

이 문제의 경우 그리디 문제이다 이 문제의 경우 Priority Queue로 풀면 쉽게 풀리는  문제였다. 일단 나는 이 문제를 보고 냅색문제 와 비슷 하다고 생각했다. 

일단 나는 이문제의 숙제의 중요도를 숙제의 점수 라고 생각 했다 이에 우선순위 큐에 과제를 끝냈을 때의 점수가 가장 높은것들 순으로 나열 시켰다.

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

우리의 테스트 케이슬 중요도 즉 과제를 맞췄을 때의 점수를 해당로직대로 내림차순 정렬 하게 되면 아래 그림 처럼 된다

우리가 실제로 과제를 한다 생각 해 보자 우리는 당연히 가장 중요한걸 될 수 있는  한 최대한 미룰 것이다 즉 첫번째 4,60은 아직 4일 차에 내가 할 일이 없으므로 60에 중요도를 가진 과제를 한다.

그후 오는 2,50은 아직 2일차에 아무일도 없으므로 50에 일을 한다 

그 후 4,40의 일은 4일 안에만 하면 되나 4일차에는 60의 일이 있으므로 4일보다 앞에 배정한다 그래서 3일 차에 40의  일을 한다

그후 3,30은 이미 3일차에 40의 일을 하였으니 3일안에 내가 할수 있는 요일은 1일차 밖에 없다 이에 30의 일은 1일 차에 한다

그후 1,20의 일은 이미 1일차에 30의 일을 하니 하지 않는다

그후 4,10의   일도 이미 4일 안에 진행 하는 일들은 다 중요도 가 높으므로 진행 하지않는다
그후 6,5는 6일차는  비어 있으므로 넣는다

즉 이문제의 풀이는 날짜를 최대한 미루데 중요한거를 우선 해서 리스트에 넣어야 한다 이에 만약 내가 4,40의 일을 한다고 가정했을 때 지금 업무를 완료했을 때의점수순으로 나열했기에 후에 나보다 낮은 일수가 나온다고 해도 점수가 높지 않고 일수도 낮고 점수도 낮은게 나올 수가 없으므로 빈공간에 채워주는 식으로 로직을 진행해야 한다

#include<iostream>
#include<queue>
using namespace std;
int day[1001] = {};
struct Compare {
    bool operator()(pair<int, int> const& p1, pair<int, int> const& p2) {
        return p1.second < p2.second;
    }
};
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pq;
int main() {
    int N;
    cin >> N;
    int num1, num2;
    int maxIdx=0;
    int result = 0;
    for (int i = 0; i < N; i++) {
        cin >> num1 >> num2;
        if (num1 > maxIdx) {
            maxIdx = num1;
        }
        pq.push({ num1,num2 });
    }

    while (!pq.empty()) {
        int x, y;
        x = pq.top().first;
        y = pq.top().second;
        pq.pop();
        if (day[x]== 0) {
            day[x] = y;
        }
        else {
            for (int i = x - 1; i > 0; i--) {
                if (day[i] == 0) {
                    day[i] = y;
                    break;
                }
            }
        }

    }
    for (int i = maxIdx; i > 0; i--) {
        result += day[i];
    }
    cout << result;
}

이 문제의 경우 나에게 여러가지 에러를 보여줌으로 여러가지 함수를 사용할 때 주의 할점을 알려줬다. 일단  이 문제의 코드는 이렇게 된다

#include <iostream>
#include <queue>
#include <vector>
#define INT_MAX 2147483647
using namespace std;
vector<int> distanceV(20002); //시작점 부터 다른 정점까지의 거리를 저장
vector<bool> visited;
void djikstra(int start, vector<pair<int, int>> dijkstraGraph[]) {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 거리, 노드 인덱스
	pq.push(make_pair(0, start));
	distanceV[start] = 0;

	while (!pq.empty()) {
		int distanceOfTo = pq.top().first;
		int toVertex = pq.top().second;
		pq.pop();

		if (distanceOfTo > distanceV[toVertex]) {
			continue;
		}

		for (int i = 0; i < (int)dijkstraGraph[toVertex].size(); i++) {
			int cost = distanceOfTo + dijkstraGraph[toVertex][i].second;
			int nextIndex = dijkstraGraph[toVertex][i].first;
			if (cost < distanceV[nextIndex]) {
				distanceV[nextIndex] = cost;
				pq.push(make_pair(cost, nextIndex));
			}

		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int vertex, edge, start;  //vertex는 정점 edge는 간선 start는 시작점을 입력 받는다.
	cin >> vertex >> edge >> start;
	vector<pair<int, int>> dijkstraGraph[20002];//다익스트라 알고리즘의 비용을 저장할 우선순위 큐
	for (int i = 1; i <= edge; i++) {
		int from, to, cost;  //from은 간선사이의 시작점,to는 도착점 , cost는 간선의 비용을 의미
		cin >> from >> to >> cost;
		dijkstraGraph[from].push_back(make_pair(to,cost));
	}
	distanceV.assign(20002, INT_MAX);
	djikstra(start, dijkstraGraph);
	for (int i = 1; i <= vertex; i++) {
		if (distanceV[i] == INT_MAX) {
			cout << "INF"<<endl;
		}
		else {
			cout << distanceV[i] << endl;
		}
	}
}

이 문제의 경우 일단 간선의 방향이 단 방향이다. 일단 이문제의 예시 input에 대한 과정의 그림을 첨부하겠다

이 그림 에서 원으로 되어 있는 그래프는 위에 dijkstra함수에 pq를 그린것이다. 밑에 배열은 distanceV를 그린것이다.

일단 처음 풀이에서

distanceV.assign(20002, INT_MAX);

이 코드를 통해 배열에 큰 값을 다 넣어주었다 이에 처음 벡터에는 INF값만 가득하다 그후 1,0 즉 시작점 1에서 도착지 1로가는 거리는 자기자신이므로 0을 넣어준다 그후 2,2순으로 pq순에서 팝되는 값과 나와 연결되어 있는 다음 인덱스의 값을 더해서 distanceV에 거리를 갱신해 준다. 즉 1이 팝되었을때는 2,3의 거릿값이 갱신된다. 이후 2가팝되었을 때는 3과 4에 연결되어있으므로 시작점부터 자기자신까지의 거리와 나랑 연결되어 있는 노드의 값을 더해서 만약 원래 그 노드까지의 거리보다 나를 통해 가는 거리가 짧으면 그 노드쪽의 값을 갱신해주고 아니면 넘어간다 이런식으로 계속 나까지의 거리와 다음 노드까지의 거리를 계속 갱신해주면서 최소 거리를 구하면 된다.