[Java] 백준 25947 선물할인 실버1

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

문제 접근 

그리디 문제!!

선물의 개수 최대 10만개 / 선물의 할인 개수가 최대 10만이니까 

브루트 포스로 풀면 시간 초과가 발생한다. 

 

구현은 간단하다. 

우리는 가장 많은 선물을 살 수 있게 할인을 적용시키면 된다. 

정답 코드 

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]); // 선물의 개수
        int b = Integer.parseInt(input[1]); // 초기 예산
        int a = Integer.parseInt(input[2]); // 할인 받을 수 있는 최대 선물 개수
        int A = a;

        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(list);
        
        int cur   = 0;
        while (cur < n){
            if(a > 0){
                b -= (list.get(cur) / 2);
                a--;
            }
            else{
                if(A == 0){
                    b -= list.get(cur);
                }
                else{
                    b -= list.get(cur - A) / 2;
                    b -= (list.get(cur) / 2);
                }
            }
            if(b < 0) break;
            cur++;
        }
        System.out.println(cur);
    }
}