[G4] 백준 6195번 Fence Repair C++ 그리디 알고리즘, 우선순위 큐

리뷰

 

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

회사에서 촉박하게 풀려니 잘 안풀렸다가 집에 오니 어떻게 풀어야 할지 생각이 났다.

 

 

전역 변수

• n : 만들어야 할 나무 판자의 개수를 저장할 변수
• pq : 만들어야 할 나무 판자의 길이를 저장할 우선순위 큐

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 만들어야 할 나무 판자의 길이를 입력 받아 pq에 push한다.
2. 변수 ans를 0으로 초기화한다.
3. pq의 크기가 1보다 클 때를 조건으로 하는 while루프를 수행한다.
4. 변수 s1, s2에 pq의 top요소를 두개 뽑아 저장한다,
5. 변수 sum에 s1 + s2를 저장하고, ans에 sum을 더해준 뒤 pq에 sum을 삽입한다.
6. while루프가 종료된 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. pq와 multiset을 통해 lower_bound로 현재 만들어야 할 나무 판자의 길이와 가장 가까운 값을 pq에 삽입해 주는 방법으로 로직을 작성하였다가 WA를 받았다.
2. top-down방식이 아닌 bottom-up방식으로 구현하여 나무 판자를 하나의 긴 나무 판자로 만드는 방법으로 접근하여 로직을 작성하였더니 AC를 받았다.

 

참고 사항

1. N은 최대 2만, 각 길이는 최대 5만까지 주어진다.
2. 안전하게 로직을 작성하기 위해 ans는 long long을 사용해 주었고, pq는 int범위로도 가능할 것이라는 판단을 내렸다.

 

정답 코드

#include <iostream>
#include <queue>
using namespace std;

int n;
priority_queue< int, vector< int >, greater< int > > pq;

int main()
{
	ios::sync_with_stdio( 0 );
	cin.tie( 0 );

	cin >> n;
	for ( int i = 0; i < n; ++i )
	{
		int l; cin >> l;
		pq.push( l );
	}

	long long ans = 0;
	while ( pq.size() > 1 )
	{
		int s1 = pq.top(); pq.pop();
		int s2 = pq.top(); pq.pop();
		int sum = s1 + s2;
		ans += sum;
		pq.push( sum );
	}

	cout << ans;
}