[백준] 1715 카드 정렬하기 c++

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

1715번: 카드 정렬하기

 

내 풀이

두 수를 더하고 다음 수에 대해 무언가를 해야한다고 생각해서 해맸다.
(a, b, c, d .. 오름 차순으로 있다면 a + b 하고 c에 대해 해야한다고 )

또한 수를 a, b, c, d, e, f 로 두고 대수적으로 풀려고 해서 꼬였다. 흔적..

그래서 힌트를 봤는데 우선순위큐가 있었다. ..

제일 작은 두 수를 더한다. 그 다음은? 이라고 생각했는데

제일 작은 두수를 계속 더해주면 되는 문제였다.

a+b가 c보다 작을 수도 있고  때문에 a+b가 어디에 들어가는지가 중요하다. 
계속 정렬을 시키기엔 오래걸리니까 우선순위큐를 사용해서 새로 만들어진 수를 큐에 넣고 제일 작은 두 수를 꺼내서 이 과정을 반복하면 된다.

이게 핵심인데 힌트를 봐버려서 ^^ ..  더 열심히 해야겠다.

다른 사람 풀이를 들도 살펴봤다.

#include<iostream>
#include<queue>

using namespace std;
int N;
priority_queue<int, vector<int>, greater<int>>q;


int main()
{
	cin >> N;
	int tmp = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> tmp;
		q.push(tmp);
	}
	int a = 0, b = 0;
	int sum = 0;
	//cout << endl;
	while (q.size() != 1)
	{
		a = q.top(); q.pop();
		b = q.top(); q.pop();
		sum += (a + b);
		q.push(a + b);
	}
	
	cout << sum;
}

다른 사람의 풀이 1

배열과 큐 하나로 푼 풀이 : 제일 작은 숫자를 고르는 풀이가 신선했다. (Get 함수)
입력을 오름차순으로 정렬한다. 큐는 제일 작은 두 숫자를 합친 숫자를 넣는다.
제일 작은 숫자를 정하는 법 : 배열에서 제일 작은 수와 큐에 제일 앞에 있는 숫자를 비교해서 더 작은 숫자를 정한다.
* queue는 오름차순으로 정렬될 수밖에 없다. ex) 20 + 20 = 40 큐에 40 이 들어간다. 그 다음 작은 숫자 2개를 a, b라고 할때   a,b>=20 이기 때문에 a+b>=40
처음 들어온 숫자를 다 썼는지, 큐에 숫자가 있는지 에 따라 제일 작은 숫자를 정해준다.

https://www.acmicpc.net/source/46460922

로그인

 

다른 사람의 풀이 2

map을 이용해서 푸셨다. 또 나와 위의 분은 두 숫자를 한번씩 더해주었는데 이 풀이는
 10 이 6개 있고 10이 제일 작다면  10 *2* 3 으로 한 번에 구해준다. 10* (2개씩 더해서 2) * (6개/2)

https://www.acmicpc.net/source/43903731

로그인