[백준] 1715번 카드정렬하기 자바 코드 & 문제풀이 방법

[ 백준 ] 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);
    }
}

 

 

문제링크

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기