[ Baekjoon - 11/12 ] - 15903번: 카드 합체 놀이

• 문제 링크 : https://www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

 

• 소요 시간 : 53분 41초

카드 합체 놀이

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

512 MB

10194

4369

3640

42.965%

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력 1 복사

3 1
3 2 6

예제 출력 1 복사

16

예제 입력 2 복사

4 2
4 2 3 1

예제 출력 2 복사

19

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 512MB
   • 문제
     
     • 카드의 개수 N [2, 1000]
       카드 합체 횟수 M [0, 15 x 1000] == [0, 15,000] (아니 나 왜 15만이라 생각했지...) 
     • 석환이가 카드 N개 중에서, 임의의 2개를 선택하고 이 카드끼리 합한 값을 다시 카드에 기록하는 루틴을 M번 반복할 때, 최소점수를 출력하는 문제
     • 여기서 점수는 모든 카드에 적힌 수의 합이다.
   • 이해
     • 문제 이해에서 어려운 점은 따로 없었다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 입출력 형태와 함께, 카드 시뮬레이션을 직접 그려보았다.
   • 그리고 총 점수형태가 어떤식으로 나올 것 같은지 직접 적어보았다.
3. 문제를 어떻게 해결할 것인가

   • 

   • 1st 접근 -  정렬하고 가장 작은 점수 2개를 선택 : 이를 N번 반복 )
     • 비록 점수 2개의 합이지만, 이것도 가장 작은 점수들을 선택하여 합친것이 가장 작은 합이기 때문에, 점수를 정렬하고 여기서 가장 작은 2개를 뽑는 방식으로 가야한다고 생각했다.
     • 원래라면 이쯤 생각하고 코드를 작성하러 갔겠지만.. 시간복잡도를 계산해보기로 했다.
     • 점수를 정렬해야하므로 O(NlogN), 2개를 뽑고 더해서 넣는 것은 O(상수),
       이를 총 M번 반복해야하므로 O(MNlogN + 상수) = 15,000 x 1000 x 3 = 4억 5천 이다. 즉, 불가능
   • 2nd 접근 -  짜피 정렬하고 가장 작은 점수 2개니까 앞 4개에서 나오지 않을까 )
     • 결론부터 말하자면 굉장히 잘못된 생각이었다.
     • 정렬한 직후에 뽑고 합치고 넣어둔 뒤에, 다시 정렬하지 않아도 앞 4개에서 나올 수 있기 때문에 한 생각이었는데, 딱 1회차에서만 허용되는 접근이었기 때문에 맞지 않았다.
   • 3rd 접근 - 우선순위 큐를 사용하자!)
     • 왜 바로 생각 못했는지 아쉬움이 아직도 남긴한다..
     • 반복할때마다 정렬이 필수적이기 때문에, 위 정렬을 간단화시킬 필요가 있었다..
     • 자료구조 중에서 우선순위 큐는 정렬을 위해 큐에 넣는 연산 logN, 빼는 연산 logN이기 때문에, 위 문제에 적절히 사용할 수 있을거라 생각했다.
4. 위 계획을 검증
   • 그리디적 접근의 대표적 문제이므로 생략
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main{
            static int N,M;
            static long min1,min2,sum;
            static PriorityQueue<Long> A;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
                StringTokenizer st = new StringTokenizer(br.readLine());
                N = Integer.parseInt(st.nextToken());
                M = Integer.parseInt(st.nextToken());
        
                A = new PriorityQueue<>();
                st = new StringTokenizer(br.readLine());
                // pq에 삽입 시간복잡도 logN, N번 반복 -> NlogN = 1000 * 3 = 3000
                for (int n = 0; n < N; n++) {
                    A.add(Long.parseLong(st.nextToken()));
                }
        
                // pq에 삽입, 삭제 시간복잡도 logN, M번 반복 -> M * (4*logN) = 150000 * 4 * 3 = 180만
                for (int m = 0; m < M; m++) {
                    min1 = A.poll();
                    min2 = A.poll();
                    A.add(min1+min2);
                    A.add(min1+min2);
                }
        
                // N개의 pq를 꺼내며 총합 연산 -> NlogN = 3000
                while(!A.isEmpty()){
                    sum+=A.poll();
                }
        
                bw.write(sum+"\n");
                bw.flush();
            }
        }

• 결과

int끼리의 합은 int범위를 초과할 수 있을 것이라 생각해서 sum변수는 long으로 두었지만, 아이러니하게도 카드 점수는 int로 선언해버려서 얻은 결과였다..

자료형에 좀 더 신경써야지 ㅠ