급하게임개발

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

이 문제의 경우 생각하는건 쉬웠다 사실 어떠한 배열에서 가장 작은 2개를 선택한 후 이를 그다음 작은애랑 더해주면 되는 문제였다 그래서 이문제를 나는 큐를 사용해서 풀고 싶었다. priority queue를 사용해서 풀고 싶었기 때문에 사실 데큐를 사용해서 풀수도 있는 문제기는 하다 데큐로 푸는 방식은 그냥 입력받은애들을 작은애들 순으로 소팅한 후 더한후 front에 넣고 다시 front에서 두개를 더한후 넣고 다시 두개 팝해서 넣고 하는 방식으로 하면 된다 이러한 로직도 priority queue에 적용이 되기 때문에 사용하면 된다 소스코드는 이렇게 된다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
int main() {
	int card;
	int n;
	int sum = 0;
	cin >> card;
	for (int i = 0; i < card; i++) {
		cin >> n;
		pq.push(n);
	}

	while (pq.size() > 1) {
		int x, y;
		x = pq.top();
		pq.pop();
		y = pq.top();
		pq.pop();
		sum += (x + y);
		pq.push(x + y);
	}
	
	cout << sum;

}

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

이 문제의 경우 사실 dfs로푸는게 간단해보였다 하지만 문제 분류가 그리디로 되어있었으니 그리디로 풀어 보겠다

이문제의 경우 A와 B가 주어졌을 경우 A에서 B를 만든다고 생각하지말고 B에서 A로 가야한다고 생각해야 잘풀리는 문제였다 B가 일단 2로 나누어지는 경우 2로 나누고 B가 10으로 나누었을 때 1이 남으면 10으로 나눈다 그후 A와 비교해서 같으면 나오고 아니면 다시 실행한다 단 B가 A보다 작아졌을 경우는 문제의 답이 존재하지 않는 경우기 때문에 -1을

출력한다.

이문제의 경우 상당히 쉬웠지만 계속 A에서 B를 만들려고 하니 시간이 많이 소모되었다.

#include <iostream>
using namespace std;
int main() {
	int A, B;
	int countnum=0;
	cin >> A >> B;
	while (true) {
		if (A == B) {
			countnum += 1;
			break;
		}
		if (A > B) {
			countnum= -1;
			break;
		}
		if (B % 10 == 1) {
			B--;
			B = B / 10;
			countnum++;
		}
		else if (B % 2 == 0) {
			B = B / 2;
			countnum++;
		}
		else {
			countnum= -1;
			break;
		}
	}
	cout << countnum;

}

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

이 문제는 풀다가 이상하다 왤케 답이 완전 다르게 나오지 하다가 보니까 내가 문제를 잘못이해하고 있었다

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

여기 나오는 이값들은 사실 순위였던 것이었다. 그래서 문제를 이상하게 풀고 있었다. 이문제는 간단히 설명하자면

하나의 성적을 기준으로 줄을 세워놓은 다음에 다음애들을 비교하여 그 줄에서 나의 다음(나보다 성적이 낮은) 애들의 다른 성적을 비교하여 나보다 성적이 낮으면 그친구를 쳐내는 방식이다 예를 들면 서류심사 성적으로 줄을 세워놓은 다음에

나보다 서려심사를 못봤는데 나보다 면접 성적 까지 낮으면 그 사람은 세지 않는 방법이다

자 위 그림을 보자 서류 성적 순대로 정렬 한다 이렇게 정렬하면 내 다음에 나오는 애는 무조건 나보다 서류 성적은 낮은 상태가 된다. 그러므로 나보다 서류성적이 낮은애랑 나의 면접성적을 비교한다 나의 다음애가 나보다 면접 성적이 높으니 count를 하고 지금까지 비교했을 때 가장 높은 성적을 maxnum에 저장해주고 countnum을 하나 증가시켜준다 즉 현재 서류성적순으로 정렬했을때 가장 높은 면접성적은 3등이다 이제 그다음에 나오는 애는 3등보다 면접 성적이 높으면 maxnum에 갱신해주고 쳐내지 않지만  다음애가 이전까지 비교해서 나온성적인 3등보다 낮으면 쳐낸다 계속 이렇게 반복하여 countnum의 값을 답으로 출력해주면 된다

#include <iostream>
#include <algorithm>
using namespace std;
pair<int, int> score[100000];
int answer[20];
int main() {
	int testnum;
	cin >> testnum;
	for (int i = 0; i < testnum; i++) {
		int countnum = 0;
		int candidatenum;
		cin >> candidatenum;
		for (int j = 0; j < candidatenum; j++) {
			cin >> score[j].first >> score[j].second;
		}
		sort(score, score + candidatenum);
		int maxscore = score[0].second;

		for (int j = 0; j < candidatenum; j++) {
			if (score[j].second <= maxscore) {
				countnum++;
				maxscore = score[j].second;
			}

		}
		answer[i] = countnum;
	}
	for (int i = 0; i < testnum; i++) {
		cout << answer[i] << '\n';
	}
}