[자바] 백준 1715 - 카드 정렬하기 (java)

 문제 : boj1715

---

 

필요 알고리즘 개념

• 그리디
  • 일정한 규칙을 정해 매번 해당 규칙을 적용시키다 보면 답이 나오는 알고리즘으로, 뭔가 알아야 하는건 아니고 그냥 그런 식으로 생각할 수 있어야 한다.
• 우선순위 큐 (Priority Queue), Min heap
  
  • 다른걸 사용해서 풀어도 되지만, 이 문제를 가장 쉽게 풀 수 있는건 우선순위 큐를 사용해 min heap으로 사용하는 것이다. 

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이 문제의 경우 잘 생각해봐야 하는게, 연산 과정의 중간 결과가 다시 연산에 사용된다. 따라서 처음 주어진 카드 묶음의 크기에 대해 뭔가 정렬을 하고 의미를 가지게 되면 틀리게 된다. 예를들어 아래의 경우를 보자.

4
1
2
2
2

순서대로 계속해서 계산을 해나갈 시, 'A=(1+2)=첫번째랑 두번째 더함, B = A+2 = A계산결과와 3번째 더함, C = B+2 = B계산결과와 4번째 더함' 처럼 진행하면 15번이 나온다. 그리고 1의 위치를 어디에 옮겨봐도(2-1-2-2, 2-2-1-2, 2-2-2-1) 최소가 15이다. 근데 위 예시의 답은 14이다.

 

 

  그럼 어떻게 해야 되냐면, 그리디 알고리즘 개념을 적용하면 된다. 원본 배열에서 시작해서 중간 계산의 결과까지 포함해서, 매번 가장 작은 2개를 뽑아 더해주면 된다. 어차피 모든 N에 대해 비교횟수는 N-1번으로 고정이고, 그렇다면 매번 가장 작은 2개의 카드 묶음을 골라 합쳐주는건 따로 증명을 안해보더라도 가장 최소임이 보장될 것이다. Min Heap으로 사용한 Priority Queue로 따지면, 매번 pq.add(pq.poll() + pq.poll())를 해주는 셈이다. 위의 예시에 대해 과정을 보자.

 

 

1. 시작은 원본 배열을 넣어준다.

 

2. 가장 작은 1과 2를 빼서 더해주면 3이 된다. 최종 출력할 결과가 sum이라 할 때, sum+=3을 해주고 3을 다시 min heap에 넣는다.

 

3. 다시 가장 작은 2개를 빼면 2+2=4가 된다. sum+=4를 해줘서 sum은 이제 7이 되었고, 4를 다시 min heap에 넣는다.

 

4. 다시 가장 작은 2개를 빼면 3+4=7이고, sum+=7해서 sum은 이제 14이다. 7을 다시 넣는다.

 

 

1개가 남은 경우엔 종료해주면 된다. 최종적으로 답은 14가 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        while(n-->0) pq.add(Integer.parseInt(br.readLine()));
        int sum = 0;
        while(pq.size() > 1) {
            int tmp = pq.poll() + pq.poll();
            sum+=tmp;
            pq.add(tmp);
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}