[java]백준 1715번: 카드 정렬하기, 그리디 알고리즘

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

1715번: 카드 정렬하기

 

 

코드

public class j1715 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();// 카드 묶음의 수 저장

		// 우선순위큐에 카드의 크기 저장
		PriorityQueue<Integer> pq = new PriorityQueue<>();

		for (int i = 0; i < N; i++) {
			int data = sc.nextInt();
			pq.add(data);
		}

		int data1 = 0;
		int data2 = 0;
		int sum = 0;

		while (pq.size() != 1) {
			// 우선순위큐를 사용해 가장 작은 크기의 그룹 두개 더해준다
			data1 = pq.poll();
			data2 = pq.poll();
			sum += data1 + data2; // 결과 sum에 더해주고
			pq.add(data1 + data2);// 다시 합쳐진 그룹을 우선순위큐에 넣어준다.

		}

		System.out.println(sum);
	}
}

 

풀이

 

그리디greedy 알고리즘:

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

 

 

그리디 알고리즘의 핵심 이론

① 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택

 

② 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사

 

③ 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못한다면 ①로 돌아가 같은 과정 반복

---

 

① 현재 카드의 개수가 가장 작은 묶음 2개를 선택해 합친다.

-> 가장 작은 묶음을 위해 우선순위큐 pq사용

 

② 합친 카드 묶음을 다시 전체 카드 묶음 속에 넣는다.

-> sum에는 계속 가장 작은 묶음 두 개 합친 것을 더해준다.

 

③ 과정 ①~②를 카드 묶음이 1개만 남을 때까지 반복합니다.

-> 1개가 남았다는건 모든 걸 합쳤기 때문에