250x250
Notice
12-08 02:11
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 1026 보물 -그리디- 자바, 코틀린 본문

알고리즘/그리디

[알고리즘] 백준 1026 보물 -그리디- 자바, 코틀린

막무가내막내 2021. 11. 23. 23:43
728x90

https://www.acmicpc.net/problem/1026

 

1026번: 보물

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거

www.acmicpc.net

 

 

 

 

백준 그리디 유형에서 보물이라는 문제를 풀어봤습니다.

A와 B 배열의 인덱스 곱의 합이 최솟값이 나와야하는데 A만 재배열이 가능하고 B는 불가능합니다.

B가 재배열이 불가하다는 말에 꽂히지말아야합니다. 

 A와 B를 오름차순으로 정렬한다음에 A의 가장 작은값과 B의 가장 큰 값 인덱스들을 서로 곱해주는게 최소의 S결과가 나오게됩니다. 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        for (int i = 0; i < N; i++) {
            B[i] = sc.nextInt();
        }
        Arrays.sort(A);
        Arrays.sort(B);
        int S = 0;
        for (int i = 0; i < N; i++) {
            S += A[i] * B[N - 1 - i];
        }
        System.out.println(S);

    }
}

 

 

[Kotlin]

package kotlin

import java.util.*


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val N = sc.nextInt()
    val A = IntArray(N)
    val B = IntArray(N)
    for (i in 0 until N) {
        A[i] = sc.nextInt()
    }
    for (i in 0 until N) {
        B[i] = sc.nextInt()
    }
    Arrays.sort(A)
    Arrays.sort(B)
    var S = 0
    for (i in 0 until N) {
        S += A[i] * B[N - 1 - i]
    }
    println(S)
}

 

 

 

https://github.com/mtjin/algorithm_practice/commit/013a0cdfdf4059b6dda7c7ae09e61ca12d9795b5

 

백준 1026 풀이 · mtjin/algorithm_practice@013a0cd

 

github.com

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!

 

 

 

 

728x90
0 Comments
댓글쓰기 폼