[문제 풀이][Java] 백준 1026번 보물

[문제 풀이][Java]  백준 1026번 보물

* 학습 목적의 게시물이나 혹시 이 게시물이 문제가 된다면 언제든 연락 부탁드립니다.

* 더 나은 풀이를 위한 훈수, 조언 등 모두 환영합니다!

문 제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입 력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고,  셋째 줄에는 B에 있는 수가 순서대로 주어진다.

N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출 력

첫째 줄에 S의 최솟값을 출력한다.

[문제 링크] 백준 1026번 보물

---

해결 방법

1. A 배열의 최솟값과 B 배열의 최댓값을 곱하여 더한다.

2. A 배열은 내림차순한다.

3. 문제 내 B 배열은 재정렬하지 않도록 하였기에 차순 정렬은 실시하지 않는다.

  * B 배열을 오름차순으로 정렬하여 A, B 배열 요소들을 순차적으로 곱하여 더해도 답에 상관은 없다.

4. B 배열을 리스트로 바꾸어 최댓값을 메소드를 통해 찾고, 내림차순된 A 정렬의 앞에서 부터 곱하여 더한다.

참고사항

[공부 필요내용]

  - 백준 풀이 제출시 사용하는 BufferReader, StringTokenizer

  - List 내 메소드 사용법

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class B1026 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		//입력받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int numberOfNumbers = Integer.parseInt(br.readLine());
		
		int[] aArray = new int[numberOfNumbers];
		int[] bArray = new int[numberOfNumbers];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < aArray.length; i++) {
			aArray[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < bArray.length; i++) {
			bArray[i] = Integer.parseInt(st.nextToken());
		}
		
		// 정수 B 배열을 리스트에 넣어 최댓값을 찾아 계산 후 삭제
		ArrayList<Integer> bList = new ArrayList<>();
		for (int i = 0; i < bArray.length; i++) {
			bList.add(bArray[i]);
		}
		
		Arrays.sort(aArray);
		
		int answer = 0;
		
		for (int i = 0; i < aArray.length; i++) {
			int max = Collections.max(bList);
			answer += (aArray[i] * max);
			bList.remove(Integer.valueOf(max));
		}
		
		System.out.println(answer);
	}
}