[C++] 백준 14729번 칠무해

 

 

메리 크리스마스~~~~~~~

크리스마스가 왔어요~~

(오예~) 케이크 먹어야지

 

 

문제

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

14729번: 칠무해

 

음... 0.001 단위까지 나왔다...

처음에는 아무 생각 없이 int로 했다가 다 잘려나갔다

 

정수만 하다보니 이번 문제는 double로 받아야 하나 해서 해보니까 출력은 정수로 나왔다.

// 틀린 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;

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

	cin >> n;
	vector<double> score(n);

	for (int i = 0; i < n; i++) {
		cin >> score[i];
	}
	sort(score.begin(), score.end());

	for (int i = 0; i < 7; i++) {
		cout << score[i] << "\n";
	}
	
	return 0;
}

 

그래서 scanf랑 printf를 사용할까 했는데 뭔가 이상하게 나온다...

너무 오랜만에 실수를 받아봐서 그런지 기억이 잘 나지 않는다.

(이래서 계속 사용해봐야되는건가)

 

 

 

안 되겠다...

다른 사람들이 어떻게 풀었는지 찾아봐야겠다.

 

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())    
#define f first
#define s second
typedef unsigned long long ll; 
const int INF = 987654321; 
int n;
double temp;
priority_queue<double> pq; 
vector<double> v; 
int main () {
	cin >> n; 

	for(int i = 0; i < n; i++){
		cin >> temp;
		if(pq.size() == 7){
			pq.push(temp); pq.pop();
		}else pq.push(temp); 
	}
	while(pq.size()){
		v.push_back(pq.top()); pq.pop();
	}
	reverse(v.begin(), v.end()); 
	for(double i : v) printf("%.3lf\n", i); 
	return 0;
}
출처: https://blog.naver.com/jhc9639/221928952290

n이 너무 크기 때문에 우선순위 큐를 사용했다고 한다. 우선순위 큐를 이용하여 값을 입력받고 크기가 7이면 값을 큐에 넣어준 후 pop을 해준. 우선순위 큐에는 내림차순으로 값이 들어가 있기 때문에 오름차순으로 바꾸기 위해 벡터에 넣고 reverse를 해주었다.

 

나는 우선순위 큐를 생각조차 못했는데... 다른 글도 보니 모든 인풋을 받아 내면 MLE를 받게 되고, 계속해서 정렬을 하여 문제를 해결하면 TLE를 받게 된다고 한다.

 

 

이 분도 보니 우선순위 큐를 이용하였다.

#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <queue>



int main()
{
	long long n;
	cin >> n;

	priority_queue<float , vector<float>, greater<float>>pq;

	for (long long i = 0; i < n; ++i)
	{
		float f;
		cin >> f;
		pq.push(f);
	}
	
	//cout << "output" << endl;
	while (!pq.empty())
	{
		for (int i = 0; i < 7; ++i)
		{
			printf("%0.3f\n", pq.top());
			pq.pop();
		}
		break;
	}

}
출처: https://velog.io/@kwt0124/14729%EB%B2%88-%EC%B9%A0%EB%AC%B4%ED%95%B4

우선순위 큐를 오름차순으로 만든 다음에 7개를 출력하셨다고 한다.

 

 

 

 

ㅠㅠ.. 이건 쉽게 풀 수 있을 줄 알았는데...

생각조차 못했다.

 

다음에 복습하면서 꼭 풀어내야지...

 

 

 

 

그럼 다들 메리 크리스마스~~~~~