[Algorithm] ๐Ÿง—โ€โ™€๏ธ๋ฐฑ์ค€ 2217 ๋กœํ”„

0. ๋ฌธ์ œ

N(1 โ‰ค N โ‰ค 100,000)๊ฐœ์˜ ๋กœํ”„๊ฐ€ ์žˆ๋‹ค. ์ด ๋กœํ”„๋ฅผ ์ด์šฉํ•˜์—ฌ ์ด๋Ÿฐ ์ €๋Ÿฐ ๋ฌผ์ฒด๋ฅผ ๋“ค์–ด์˜ฌ๋ฆด ์ˆ˜ ์žˆ๋‹ค. ๊ฐ๊ฐ์˜ ๋กœํ”„๋Š” ๊ทธ ๊ตต๊ธฐ๋‚˜ ๊ธธ์ด๊ฐ€ ๋‹ค๋ฅด๊ธฐ ๋•Œ๋ฌธ์— ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ฌผ์ฒด์˜ ์ค‘๋Ÿ‰์ด ์„œ๋กœ ๋‹ค๋ฅผ ์ˆ˜๋„ ์žˆ๋‹ค.

ํ•˜์ง€๋งŒ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋กœํ”„๋ฅผ ๋ณ‘๋ ฌ๋กœ ์—ฐ๊ฒฐํ•˜๋ฉด ๊ฐ๊ฐ์˜ ๋กœํ”„์— ๊ฑธ๋ฆฌ๋Š” ์ค‘๋Ÿ‰์„ ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๋‹ค. k๊ฐœ์˜ ๋กœํ”„๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ค‘๋Ÿ‰์ด w์ธ ๋ฌผ์ฒด๋ฅผ ๋“ค์–ด์˜ฌ๋ฆด ๋•Œ, ๊ฐ๊ฐ์˜ ๋กœํ”„์—๋Š” ๋ชจ๋‘ ๊ณ ๋ฅด๊ฒŒ w/k ๋งŒํผ์˜ ์ค‘๋Ÿ‰์ด ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค.

๊ฐ ๋กœํ”„๋“ค์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ๋กœํ”„๋“ค์„ ์ด์šฉํ•˜์—ฌ ๋“ค์–ด์˜ฌ๋ฆด ์ˆ˜ ์žˆ๋Š” ๋ฌผ์ฒด์˜ ์ตœ๋Œ€ ์ค‘๋Ÿ‰์„ ๊ตฌํ•ด๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋ชจ๋“  ๋กœํ”„๋ฅผ ์‚ฌ์šฉํ•ด์•ผ ํ•  ํ•„์š”๋Š” ์—†์œผ๋ฉฐ, ์ž„์˜๋กœ ๋ช‡ ๊ฐœ์˜ ๋กœํ”„๋ฅผ ๊ณจ๋ผ์„œ ์‚ฌ์šฉํ•ด๋„ ๋œ๋‹ค.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— ์ •์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ๋กœํ”„๊ฐ€ ๋ฒ„ํ‹ธ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ค‘๋Ÿ‰์ด ์ฃผ์–ด์ง„๋‹ค. ์ด ๊ฐ’์€ 10,000์„ ๋„˜์ง€ ์•Š๋Š” ์ž์—ฐ์ˆ˜์ด๋‹ค.

์ถœ๋ ฅ
์ฒซ์งธ ์ค„์— ๋‹ต์„ ์ถœ๋ ฅํ•œ๋‹ค.


1. ์•„์ด๋””์–ด

1) ๋กœํ”„๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ
2) 1,2, ... k๊ฐœ๋กœ ๋ถ„์‚ฐ์‹œ์ผฐ์„ ๋•Œ์˜ w์˜ max๊ฐ’์„ ์ฐพ์Œ

2. ํ•ต์‹ฌ ํ’€์ด

1) ๋กœํ”„๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ

Arrays.sort(arr);

2) 1,2, ... k๊ฐœ๋กœ ๋ถ„์‚ฐ์‹œ์ผฐ์„ ๋•Œ์˜ w์˜ max๊ฐ’์„ ์ฐพ์Œ

for(int i=0; i<k; i++) 
			w = Math.max(w, (k-i)*arr[i]);

3. ์ฝ”๋“œ

import java.io.*;
import java.util.Arrays;
public class Greedy_2 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int k = Integer.parseInt(br.readLine());
		int w = -1;
		int arr[] = new int[k];
		
		for(int i=0; i<k; i++) 
			arr[i] = Integer.parseInt(br.readLine());		
		
		Arrays.sort(arr);
		
		for(int i=0; i<k; i++) 
			w = Math.max(w, (k-i)*arr[i]);
		
		System.out.println(w);
	}
}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณต~

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ