정보
1. 소요시간 : 40분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 그리디 알고리즘, 우선순위 큐
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/1715
8. 푼 날짜 : 2023.03.06
1. 사고 과정
우선 처음에는 이게 골드문제라고 ? 라는 생각이 들었다. 그냥 자료를 정렬하고 난 뒤 가장 낮은 것부터 차례대로 더해주면 된다고 생각했다. 3분만에 그렇게 제출했는데 틀렸다고 나왔고 맞왜틀? 을 시전했다. (이럴 때가 많다... )
내가 직접 테스트케이스를 만들어보고 해봤는데 우선 내 생각이 틀렸다는 걸 알게 되었다. 그렇다면 어떤 방법을 써야할까 ?? 고민해봤는데 생각이 나질 않았다. 30분 째에 접어 들었을 때 문제 유형을 보기로 했다.
'우선순위 큐' 라는 단어를 보자마자 한 번 더 머리에 망치를 맞은 기분이 들었다. 띠용 ??하고 한 3분 정도 생각해봤는데 바로 예외를 생각해낼 수 있었다.
무조건 정렬한다고 해서는 안 된다는 것. 정렬하고 더해주었는데 그 값이 그 다음 값보다 크다면 ?? 최소값이 될 수 없다.
그 후에는 바로 문제를 풀 수 있었다.
2. 풀이 방법
- 우선순위 큐에 자료를 다 넣는다.
- 우선순위 큐의 사이즈가 2 이상이라면 2개를 빼서 더한다. 더한 값을 add 라는 변수에 저장하고, sum에는 계속해서 add를 더한다. 그리고 add를 다시 우선순위 큐에 넣어준다.
3. 소스코드
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb=new StringBuilder();
int n=Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq=new PriorityQueue<>();
for(int i=0;i<n;i++) {
int k=Integer.parseInt(br.readLine());
pq.add(k);
}
int sum=0;
while(pq.size()>1) {
int add=pq.poll()+pq.poll();
sum+=add;
pq.add(add);
}
System.out.println(sum);
}
}4. 결과
5. 회고
그리디 알고리즘이 너무 부족하다고 느껴지는 문제였다. 이 문제는 프로그래머스의 더 맵게 (https://school.programmers.co.kr/learn/courses/30/lessons/42626) 문제와 비슷하다고 생각한다. 그 문제에서는 '가장 낮은 것 2개를 더하고, 그것과 다시 비교한다' 라는 것을 문제에서 충분히 유도해낼 수 있었다. 그런데 이 문제에서는 그것을 유도해내는게 쉽지 않았다.
하루에 백준 1문에 이상 푸는 것을 목표로 하고 있다.
https://solved.ac/profile/anwlro0212
