백준_1246 온라인 판매(자바) / 그리디

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_1246 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =  new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M =Integer.parseInt(st.nextToken());
		
		ArrayList<Integer> arr = new ArrayList<>();
		
		for (int i = 0; i < M; i++) {
			arr.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(arr);
		
		int ans = 0;
		int max = 0;
		
		for (int i = 0; i < M; i++) {
			int tmp = arr.get(i);
			int tmpsum = 0;
			
			if(M-i<N) {
				tmpsum = tmp * (M-i);
			}else {
				tmpsum = tmp * N;
			}
			
			if(tmpsum>max) {
				max = tmpsum;
				ans = tmp;
			}
		}
		System.out.println(ans + " "+ max);
	}
}

 

※ 내 생각

이 문제는 그리디 알고리즘을 활용하는 문제입니다.

먼저 값을 입력한 다음에 정렬을 진행합니다.
정렬해준 값을 기준으로 for문을 돌려서 각 위치에서의 최댓값을 구해줍니다.

이 때, M과 N의 크기를 고려해서 진행하면 됩니다.