N(1 โค N โค 100,000)๊ฐ์ ๋กํ๊ฐ ์๋ค. ์ด ๋กํ๋ฅผ ์ด์ฉํ์ฌ ์ด๋ฐ ์ ๋ฐ ๋ฌผ์ฒด๋ฅผ ๋ค์ด์ฌ๋ฆด ์ ์๋ค. ๊ฐ๊ฐ์ ๋กํ๋ ๊ทธ ๊ตต๊ธฐ๋ ๊ธธ์ด๊ฐ ๋ค๋ฅด๊ธฐ ๋๋ฌธ์ ๋ค ์ ์๋ ๋ฌผ์ฒด์ ์ค๋์ด ์๋ก ๋ค๋ฅผ ์๋ ์๋ค.
ํ์ง๋ง ์ฌ๋ฌ ๊ฐ์ ๋กํ๋ฅผ ๋ณ๋ ฌ๋ก ์ฐ๊ฒฐํ๋ฉด ๊ฐ๊ฐ์ ๋กํ์ ๊ฑธ๋ฆฌ๋ ์ค๋์ ๋๋ ์ ์๋ค. k๊ฐ์ ๋กํ๋ฅผ ์ฌ์ฉํ์ฌ ์ค๋์ด w์ธ ๋ฌผ์ฒด๋ฅผ ๋ค์ด์ฌ๋ฆด ๋, ๊ฐ๊ฐ์ ๋กํ์๋ ๋ชจ๋ ๊ณ ๋ฅด๊ฒ w/k ๋งํผ์ ์ค๋์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
๊ฐ ๋กํ๋ค์ ๋ํ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, ์ด ๋กํ๋ค์ ์ด์ฉํ์ฌ ๋ค์ด์ฌ๋ฆด ์ ์๋ ๋ฌผ์ฒด์ ์ต๋ ์ค๋์ ๊ตฌํด๋ด๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ชจ๋ ๋กํ๋ฅผ ์ฌ์ฉํด์ผ ํ ํ์๋ ์์ผ๋ฉฐ, ์์๋ก ๋ช ๊ฐ์ ๋กํ๋ฅผ ๊ณจ๋ผ์ ์ฌ์ฉํด๋ ๋๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ N์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ ๊ฐ ๋กํ๊ฐ ๋ฒํธ ์ ์๋ ์ต๋ ์ค๋์ด ์ฃผ์ด์ง๋ค. ์ด ๊ฐ์ 10,000์ ๋์ง ์๋ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ต์ ์ถ๋ ฅํ๋ค.
1) ๋กํ๋ฅผ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
2) 1,2, ... k๊ฐ๋ก ๋ถ์ฐ์์ผฐ์ ๋์ w์ max๊ฐ์ ์ฐพ์
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]);
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);
}
}
์ฑ๊ณต~