[코딩테스트] 백준(BAEKJOON) - 보물(Java, 1026번)

안녕하세요~

오늘은 주말인 만큼 열심히 코테 준비를 해보고자 합니다.

요즘 Greedy관련 문제들을 풀어보는데 아직은 초보 단계가 그런가 술술풀리네요~

자신감을 얻어가고 있습니다.

 

오늘 이번에 풀어볼 문제는 보물 문제입니다.

원리는 간단하니 같이 만나~ 보시죠!

 

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

1026번: 보물

 

문제링크입니다~

 

그러면 제가 작성한 풀이를 만나보시죠~

 

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.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
				BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
				
				int N=Integer.parseInt(bf.readLine());
				
				List<Integer> A=new ArrayList<>();
				List<Integer> B=new ArrayList<>();
				
				String[] lineA=bf.readLine().split(" ");
				String[] lineB=bf.readLine().split(" ");
				
				for(int i=0;i<N;i++)
				{
					A.add(Integer.parseInt(lineA[i]));
					B.add(Integer.parseInt(lineB[i]));
				}
				
				Collections.sort(A);
				Collections.sort(B, Collections.reverseOrder());
				
				int sum=0;
				
				for(int i=0;i<N;i++)
				{
					sum=sum+(A.get(i)*B.get(i));
				}
				
				System.out.println(sum);
	}

}

네~ 문제입니다.

어떠신가요? 코드만 보고 감이 오실까요?

A List와 B List의 각각 원소를 대칭 시켜서  곱하고 최소값을 만들어야합니다~

 

최. 소. 값을 만들려면?!

 

가장 작은 수에 가장 큰 수를 곱해서 수가 커지지 않게 하자!라는 원리를 갖고 풀어보시면 되겠습니다~

 

그렇기에 A List에는 Collections.sort를 이용해서 오름차순~

그리고 B List에는 Collections.sort(Collections.reverseOrder())를 이용해 내림차순~으로 정렬했습니다.

 

그러면 A의 가장 작은 원소와 B의 가장 큰 원소가 곱해지고

A의 가장 큰 원소가 B의 가장 작은 원소와 곱해지겠죠?

 

이렇게 작성해주시면 되겠~습니다.

 

감사합니다. 😊😊