[코드트리] 스승의 은혜2

         아이디어        

 

N명의 학생에게 B만큼의 예산으로 선물을 주려고 하는데 

한 학생의 선물만 반값으로 할인받을 수 있다 

반값 할인할 학생을 하나 선택한 다음에 가격이 낮은 순서대로 B 예산 전까지 확인하여 선물을 준다 

 

         소스코드        

import java.io.*;
import java.util.*;
public class Main {
    static int[] price;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =  new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 학생수
        int B = Integer.parseInt(st.nextToken()); // 예산
        price = new int[N];
        for(int n = 0; n < N; n++){
            price[n] = Integer.parseInt(br.readLine());
        }
        int ans = 0;
        for(int i = 0; i < N; i++) {
            int[] temp = new int[N];
            for(int j = 0; j < N; j++){
                temp[j] = price[j];
            }            
            temp[i] = price[i]/2; // 할인할 학생 

            Arrays.sort(temp);
            int cnt = 0;
            int student = 0;
            for(int n = 0; n < N; n++) {
                if(cnt + temp[n] > B) { // 예산 초과하는 경우 
                    break;
                }
                cnt += temp[n];
                student += 1;
            }
            ans = Math.max(ans, student);
        }
        System.out.println(ans);
    }
}