https://programmers.co.kr/learn/courses/30/lessons/12982
[ λ¬Έμ ]
Sμ¬μμλ κ° λΆμμ νμν λ¬Όνμ μ§μν΄ μ£ΌκΈ° μν΄ λΆμλ³λ‘ λ¬Όνμ ꡬ맀νλλ° νμν κΈμ‘μ μ‘°μ¬νμ΅λλ€. κ·Έλ¬λ, μ 체 μμ°μ΄ μ ν΄μ Έ μκΈ° λλ¬Έμ λͺ¨λ λΆμμ λ¬Όνμ κ΅¬λ§€ν΄ μ€ μλ μμ΅λλ€. κ·Έλμ μ΅λν λ§μ λΆμμ λ¬Όνμ κ΅¬λ§€ν΄ μ€ μ μλλ‘ νλ €κ³ ν©λλ€.
λ¬Όνμ κ΅¬λ§€ν΄ μ€ λλ κ° λΆμκ° μ μ²ν κΈμ‘λ§νΌμ λͺ¨λ μ§μν΄ μ€μΌ ν©λλ€. μλ₯Ό λ€μ΄ 1,000μμ μ μ²ν λΆμμλ μ νν 1,000μμ μ§μν΄μΌ νλ©°, 1,000μλ³΄λ€ μ μ κΈμ‘μ μ§μν΄ μ€ μλ μμ΅λλ€.
λΆμλ³λ‘ μ μ²ν κΈμ‘μ΄ λ€μ΄μλ λ°°μ΄ dμ μμ° budgetμ΄ λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μ΅λ λͺ κ°μ λΆμμ λ¬Όνμ μ§μν μ μλμ§ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
[ μ ν쑰건 ]
- dλ λΆμλ³λ‘ μ μ²ν κΈμ‘μ΄ λ€μ΄μλ λ°°μ΄μ΄λ©°, κΈΈμ΄(μ 체 λΆμμ κ°μ)λ 1 μ΄μ 100 μ΄νμ λλ€.
- dμ κ° μμλ λΆμλ³λ‘ μ μ²ν κΈμ‘μ λνλ΄λ©°, λΆμλ³ μ μ² κΈμ‘μ 1 μ΄μ 100,000 μ΄νμ μμ°μμ λλ€.
- budgetμ μμ°μ λνλ΄λ©°, 1 μ΄μ 10,000,000 μ΄νμ μμ°μμ λλ€.
[ μ μΆλ ₯ μ ]
d | budget | result |
[1,3,2,5,4] | 9 | 3 |
[2,2,3,3] | 10 | 4 |
μ μΆλ ₯ μ μ€λͺ
μ μΆλ ₯ μ #1
κ° λΆμμμ [1μ, 3μ, 2μ, 5μ, 4μ]λ§νΌμ κΈμ‘μ μ μ²νμ΅λλ€. λ§μ½μ, 1μ, 2μ, 4μμ μ μ²ν λΆμμ λ¬Όνμ ꡬ맀ν΄μ£Όλ©΄ μμ° 9μμμ 7μμ΄ μλΉλμ΄ 2μμ΄ λ¨μ΅λλ€. νμ μ νν μ μ²ν κΈμ‘λ§νΌ μ§μν΄ μ€μΌ νλ―λ‘ λ¨μ 2μμΌλ‘ λλ¨Έμ§ λΆμλ₯Ό μ§μν΄ μ£Όμ§ μμ΅λλ€. μ λ°©λ² μΈμ 3κ° λΆμλ₯Ό μ§μν΄ μ€ λ°©λ²λ€μ λ€μκ³Ό κ°μ΅λλ€.
- 1μ, 2μ, 3μμ μ μ²ν λΆμμ λ¬Όνμ ꡬ맀ν΄μ£Όλ €λ©΄ 6μμ΄ νμν©λλ€.
- 1μ, 2μ, 5μμ μ μ²ν λΆμμ λ¬Όνμ ꡬ맀ν΄μ£Όλ €λ©΄ 8μμ΄ νμν©λλ€.
- 1μ, 3μ, 4μμ μ μ²ν λΆμμ λ¬Όνμ ꡬ맀ν΄μ£Όλ €λ©΄ 8μμ΄ νμν©λλ€.
- 1μ, 3μ, 5μμ μ μ²ν λΆμμ λ¬Όνμ ꡬ맀ν΄μ£Όλ €λ©΄ 9μμ΄ νμν©λλ€.
3κ° λΆμλ³΄λ€ λ λ§μ λΆμμ λ¬Όνμ κ΅¬λ§€ν΄ μ€ μλ μμΌλ―λ‘ μ΅λ 3κ° λΆμμ λ¬Όνμ κ΅¬λ§€ν΄ μ€ μ μμ΅λλ€.
μ μΆλ ₯ μ #2
λͺ¨λ λΆμμ λ¬Όνμ ꡬ맀ν΄μ£Όλ©΄ 10μμ΄ λ©λλ€. λ°λΌμ μ΅λ 4κ° λΆμμ λ¬Όνμ κ΅¬λ§€ν΄ μ€ μ μμ΅λλ€.
[ νμ΄ ]
import java.util.Arrays;
class Solution {
public int solution(int[] d, int budget) {
int answer = 0;
Arrays.sort(d);
int sumnum = 0;
for(int i = 0; i < d.length; i++) {
if(sumnum>budget) {
break;
}
sumnum += d[i];
answer ++;
}
return answer;
}
}