[프로그래머스] 예산 - Java

https://programmers.co.kr/learn/courses/30/lessons/12982

코딩테스트 연습 - 예산

아니 이걸 왜 DP라고 생각하고 끙끙댔지 ㅋㅋㅋㅋ

어떤지 난이도 1에 있는게 이상하다 싶었다

 

이 문제는 그리디로 접근하면 된다.

일단 d를 오름차순으로 정렬하고 budget이 넘지 않을때까지 첫번째 원소부터 선택해나가면 된다.

결론은 매우 간단한 문제였다..

 

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        Arrays.sort(d);

        int sum = 0;
        int i;

        for (i = 0; i < d.length; i++) {
            if (sum + d[i] > budget) break;

            sum += d[i];
        }

        return i;
    }
}