내가 개발해볼게!!
[BOJ] 백준 15903번: 카드 합체 놀이(Java) 본문
https://www.acmicpc.net/problem/15903
문제
입력
첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.
두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)
출력
첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.
난이도
실버 5
Sol 1
배열을 정렬한 뒤 최솟값 두 개를 더한 값을 반영하는 과정을 m번 반복한다. 모두 반복한 후 배열에 저장된 모든 값을 더한다.
직관적이고 간단한 로직이지만 매번 배열을 정렬해야 해서 시간이 오래 걸린다..
public class B15903_카드합체놀이 {
static int n, m;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer token = new StringTokenizer(bf.readLine());
n = Integer.parseInt(token.nextToken());
m = Integer.parseInt(token.nextToken());
long[] cards = new long[n];
token = new StringTokenizer(bf.readLine());
for(int i=0; i<n; i++){
cards[i] = Integer.parseInt(token.nextToken());
}
for(int i=0; i<m; i++){
Arrays.sort(cards);
long add = cards[0] + cards[1];
cards[0] = add;
cards[1] = add;
}
long sum = 0;
for(long i : cards){
sum += i;
}
System.out.println(sum);
}
}
Sol 2
우선순위 큐를 사용해 풀 수 있다. 낮은 수가 우선순위를 가지는 큐를 사용하면 큐에 수를 add할 때마다 오름차순으로 정렬되어 들어가기 때문에 별도의 정렬 과정 없이도 최솟값을 바로 뽑아낼 수 있어 Sol 1에 비해 시간이 단축된다.
public class B15903_카드합체놀이 {
static int n, m;
static long sum = 0;
static PriorityQueue<Long> input;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer token = new StringTokenizer(bf.readLine());
n = Integer.parseInt(token.nextToken());
m = Integer.parseInt(token.nextToken());
input = new PriorityQueue<>();
token = new StringTokenizer(bf.readLine());
for(int i=0; i<n; i++){
input.add(Long.parseLong(token.nextToken()));
}
// input
long x = 0, y = 0;
for(int i=0; i<m; i++){
if(!input.isEmpty()) x = input.poll();
if(!input.isEmpty()) y = input.poll();
long add = x + y;
input.add(add);
input.add(add);
}
sum = 0;
while(!input.isEmpty()){
sum += input.poll();
}
// operation
System.out.println(sum);
// output
}
}
😅
카드에 적힌 각 자연수들의 최댓값이 1,000,000이기 때문에 배열과 변수의 타입을 long으로 선언해야 하지만, int로 선언해 틀렸다.
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 백준 15900번: 나무 탈출(Java) (0) | 2023.09.07 |
---|---|
[BOJ] 백준 1992번: 쿼드 트리(Java) (0) | 2023.09.01 |
[BOJ] 백준 11403번: 경로 찾기(Java) (0) | 2023.08.25 |
[BOJ] 백준 20055번: 컨베이어 벨트 위의 로봇 (0) | 2023.08.23 |
[BOJ] 백준 2343번: 기타 레슨(Java) (0) | 2023.08.17 |