728x90
반응형
필요 알고리즘 개념
- 그리디
- 일정한 규칙을 정해 매번 해당 규칙을 적용하다보면 답이 나오는 알고리즘
- 우선순위 큐
- 우선순위 큐는 자동으로 수가 우선순위대로 정렬된다.
- 우선 순위 큐를 사용해 mini heap을 사용
풀이
- 위 문제의 핵심은 연산 과정의 중간 결과가 다시 연산에 사용된다는 것
- 매번 가장 작은 2개를 뽑아 더해주면 된다
백준문제의 예시
1. 3개의 수를 받는다.
10 / 20 / 40
2. 연산 시작
10+20 =30
30을 합계에 포함한다.
중간 연산의 30을 다시 큐에 넣어준다.
30/40
3. 두 번째 연산
30+40
70을 합계에 포함한다.
결과 = 100
코드구현
import java.util.PriorityQueue;
import java.util.Scanner;
public class QueP1715 {
static int X;
static int sum;
static PriorityQueue<Integer> pq;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
X = sc.nextInt();
pq = new PriorityQueue();
for (int i = 0; i < X; i++) {
pq.offer(sc.nextInt());
}
while (pq.size() > 1) {
int tmp =pq.poll()+pq.poll();
sum += tmp;
pq.add(tmp);
}
System.out.println(sum);
}
}
결과
BuffredReader를 사용하여 값을 입력받았을 때 결과
확연한 차이가 있음을 알 수 있다.
입력받는 수가 많을 경우에는 BuffredReader를 사용하자!
728x90
반응형
'문제 풀이 > 백준 문제풀이' 카테고리의 다른 글
[백준12789-자바/우선순위큐] 도키도키 간식드리미 (0) | 2024.03.20 |
---|---|
[백준 1427 - 자바/ 선택정렬] 소트인사이드 (0) | 2024.03.20 |
[백준 2164-Java ] 카드2 + Queue에 대한 설명 (0) | 2024.03.17 |
[백준 - 11659/ Java] 구간합 구하기 (4) | 2024.03.12 |
[백준 - 2178/ 자바(Java)] 미로 탐색 문제 BFS로 해결하기 (1) | 2024.02.28 |