[ 백준 ] 1715번 카드정렬하기 자바 코드 & 문제풀이 방법
문제설명
생각해야 할 요소
1. 처음엔 문제가 이해가 잘 안갔다. 문제에서 정렬된 두 묶음의 숫자카드가 있다고 나와있는데, 이 말이 입력값이 정렬이 된 상태로 들어온다는 건가? 헷갈렸다.
2. 문제를 읽다가 생각해낸 풀이는, 최소한의 비교 횟수가 나오려면 숫자가 작은 것들끼리 더해야 한다는 한다는 것이었다.
- 간단하게 생각해서 처음 나온 숫자랑 두번째 나온 숫자는 N-1 번 나올거고, 그 다음은 N-2, N-3 나오는거 아닌가? 해서 풀었다.
- 결과는 틀렸습니다!
- 그 이유는, 다른 예시를 보면 이해가 확실히 갈 것이다.
- 백준에서 주어진 예시에는 (10 + 20 ) < 40 이라 한번에 캐치하기 어려웠을 수도 있다.
- 이 문제의 패턴은 더해진 숫자가 또 더해지고 더해지는 패턴인데, [20, 40, 50, 70] 의 경우를 생각해봤다.
- 더해진 값이 다음의 값보다 큰 것을 확인했다. 더한 값이 pq 안의 값보다 클 수도 있는 경우가 있다!
- 값을 더해서 pq로 add 하면 된다.
문제풀이 방법
1. Priority Queue 우선순위 큐를 사용한다.
2. 더해진 숫자를 우선순위 큐에 넣고 queue가 빈 값이 될 때까지 돌려주고 pq에서 나온 값들을 다 더해주면 끝난다!
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class CardSorting_1715 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long ans = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i=0; i<N; i++) pq.add(Integer.parseInt(br.readLine()));
int cnt = 0;
int value = 0;
while (!pq.isEmpty()) {
if(cnt % 2 == 0) value = pq.poll();
else {
value += pq.poll();
pq.add(value);
ans += value;
}
cnt++;
}
System.out.println(ans);
}
}
문제링크
LIST
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1005번 ACM Craft 문제풀이 방법 feat. 자바 (0) | 2020.11.24 |
---|---|
[백준] 19640번 화장실의 규칙 자바 코드 및 문제풀이 방법 (0) | 2020.11.11 |
[백준] 연구소 14502번 - JAVA (0) | 2020.11.07 |
[백준] 경쟁적 전염 18405- JAVA (0) | 2020.11.05 |
[백준] 치킨배달 15686 - JAVA (0) | 2020.11.05 |