백준 #15903 카드 합체 놀이
문제 설명👩🏫
자연수가 쓰여진 카드를 n장에서 x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.
이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만들어라.
입출력 예
입력
3 1
3 2 6
출력
16
내 코드💻
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
StringTokenizer st = new StringTokenizer(str, " ");
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
PriorityQueue<Long> pq = new PriorityQueue <>();
str = br.readLine();
st = new StringTokenizer(str, " ");
for(int i=0;i<n;i++){
pq.add(Long.parseLong(st.nextToken()));
}
for(int i=0;i<m;i++){
long a = pq.poll();
long b = pq.poll();
long abSum = a+b;
pq.add(abSum);
pq.add(abSum);
}
long sum = 0;
for(Long i:pq){
sum += i;
}
System.out.println(sum);
}
}설명💡
가장 작은 두 수를 반복해서 더해야하기 때문에, 우선순위 큐인 PriorityQueue 큐를 사용해서 문제를 풀어야한다. 큐에 입력을 받으면 크기 순서대로 저장되기 때문에 굳이 정렬을 할 필요가 없어진다.
두 개씩 꺼내서 더하고, 더한 값을 큐에 2번 넣어준다. 반복문이 끝나고 다 더하면 정답이 된다.
실패한 코드(1차 시도)😟
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
StringTokenizer st = new StringTokenizer(str, " ");
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
str = br.readLine();
st = new StringTokenizer(str, " ");
for(int i=0;i<n;i++){
list.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(list);
for(int i=0;i<m;i++){
int nextNum = list.get(0)+list.get(1);
list.set(0,nextNum);
list.set(1,nextNum);
Collections.sort(list);
}
int sum=0;
for(int i=0;i<n;i++){
sum += list.get(i);
}
System.out.println(sum);
}
}음.. 컴파일 에러가 뜨는데 왜 그런지는 안뜬다..
근데 아마 정렬을 여러번해서 그런거 같긴하다..
실수한 부분😟
첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.
두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)
↑ 입력에 이렇게 주어지는데 여기서도 변수에
int가 아닌 long을 사용했어야 했다..
느낀 점 및 궁금한 점🍀
우선순위 큐와 힙에 대해서 더 공부할 수 있는 문제였다. long을 사용 해야할 때를 명확하게 구분해야겠다..!!
참고자료🤓
