[伯俊]1715カードソート
問題の定義
質問する
きちんとした数字カードが2束あると言ってください.1束あたりのカードの数をA、Bと言います.普通は2束を合わせて1つ作って、A+Bの比較をします.例えば、20枚のデジタルカードと30枚のデジタルカードの組み合わせを50回比較する必要がある.
多くのデジタルカードが机の上に縛られている.2束に分けると、選択順によって比較回数が大きく異なります.例えば、10枚、20枚、40枚のギフトバッグがあれば、10枚と20枚のギフトバッグを合わせ、30枚のギフトバッグと40枚のギフトバッグを合わせて(10+20)+(30+40)=100回の比較が必要です.しかし10枚と40枚を合わせた後、50枚と20枚を加えると(10+40)+(50+20)=120回の比較が必要なので非効率的な方法です.
N個のデジタルカードグループの各時間を指定すると、少なくとも何回の比較が必要かを求めるプログラムを作成します.
入力
1行目はNです.(1≦N≦100000)は、N行においてデジタルカード群の各サイズを与える.デジタルカードグループのサイズは1000以下の整数です.
しゅつりょく
1行目に最小比較回数を出力します.
問題を解く
解題ロジック
解題ロジック
Array
の順に並べ替え、前から積算加算を行います.でも間違ってる!最初の20 25 30 35 50のようなカードであれば、中間20+25=45で、後に加えた値35よりも大きく、この場合、20+25、30+35、さらに20+25の45を加えると、比較回数が少なくなります.
キューから数値アルゴリズムを抽出
//큐에서 가장 작은 숫자부터 뽑아서 계산
int temp_sum = 0;
int result = 0;
while (pq.size() > 1) {
temp_sum = pq.poll() + pq.poll();
result = result + temp_sum;
pq.add(temp_sum);
}
System.out.println(result);
Priority Queue
数字が1つしかないと比べ物にならないqueue
ドアを止めて、数字があれば演算を続けます.while
最初の2つの数字を選んで、最小の2つの数字を取って、もう1つの値を加えます.temp_sum
全ての比較回数の積算値でなければならないのでループを1回回るごとに継続result
temp_sum
において、現在1つの値を加算pq
上記論理において前の2つの値が後の1つの値よりも少ない場合を防止・比較することができる.temp_sum
終了!完全なコード package Greedy;
import java.util.PriorityQueue;
import java.util.Scanner;
public class BOJ1715 {
public static void main(String[] args) {
//작은 숫자 뽑기 위해서 Integer형 priority queue 사용
PriorityQueue<Integer> pq = new PriorityQueue<>();
//초기화 및 입력 받아 배열 채우기
Scanner s = new Scanner(System.in);
int N = s.nextInt();
for (int i = 0; i < N; i++) {
pq.add(s.nextInt());
}
//큐에서 가장 작은 숫자부터 뽑아서 계산
int temp_sum = 0;
int result = 0;
while (pq.size() > 1) {
temp_sum = pq.poll() + pq.poll();
result = result + temp_sum;
pq.add(temp_sum);
}
System.out.println(result);
}
}
Reference
この問題について([伯俊]1715カードソート), 我々は、より多くの情報をここで見つけました
https://velog.io/@dandev_sw/백준-1715-카드-정렬하기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
package Greedy;
import java.util.PriorityQueue;
import java.util.Scanner;
public class BOJ1715 {
public static void main(String[] args) {
//작은 숫자 뽑기 위해서 Integer형 priority queue 사용
PriorityQueue<Integer> pq = new PriorityQueue<>();
//초기화 및 입력 받아 배열 채우기
Scanner s = new Scanner(System.in);
int N = s.nextInt();
for (int i = 0; i < N; i++) {
pq.add(s.nextInt());
}
//큐에서 가장 작은 숫자부터 뽑아서 계산
int temp_sum = 0;
int result = 0;
while (pq.size() > 1) {
temp_sum = pq.poll() + pq.poll();
result = result + temp_sum;
pq.add(temp_sum);
}
System.out.println(result);
}
}
Reference
この問題について([伯俊]1715カードソート), 我々は、より多くの情報をここで見つけました https://velog.io/@dandev_sw/백준-1715-카드-정렬하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol