1, 4, 5 λμ μ μ΄μ©νμ¬ 8μμ κ±°μ¬λ¬μ£ΌκΈ° μν΄
νμν μ΅μ λμ μ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±ν΄λ³΄μΈμ.
μ λ¬Έμ λ₯Ό 보면 λΉμ°ν ν° λμ λΆν° μ°λ κ²μ΄ μ’μ 보μ λλ€.
νμ§λ§ ν° λμ λΆν° μ¬μ©νκ² λλ©΄ 5 + 1 + 1 + 1μ΄λ―λ‘ 4κ°μ λμ μ΄ νμνμ§λ§,
4 + 4 μμ 8 μ΄λ―λ‘ μ΅μ λμ μ μλ 2κ° λ©λλ€.
κ·Έλ°λ° λ€μ κ²½μ°λ μ΄λ¨κΉμ?
1, 5, 10, 20 λμ μ μ΄μ©νμ¬ 78μμ κ±°μ¬λ¬μ£ΌκΈ° μν΄
νμν μ΅μ λμ μ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±ν΄λ³΄μΈμ.
μ΄ κ²½μ°μλ ν° λμ λΆν° κ±°μ¬λ¬μ£Όλ κ²μ΄ νμ μ’μ΅λλ€.
κ·Έ μ΄μ λ μ£Όμ΄μ§ λμ λ€μ΄ μ λΆ λ°°μκ΄κ³μ λμ¬μκΈ° λλ¬Έμ λλ€.
κ·Έλ κΈ°μ ν° λμ μ΄ μ¬μ©μ΄ κ°λ₯νλ€λ©΄, μμ λμ μ μ¬μ©νλ κ²λ³΄λ€ νμ μ’μ μ νμ΄ λλ κ²μ λλ€.
λ°λΌμ λ°°μ κ΄κ³μ λμ¬μλ λμ μ΄ μ£Όμ΄μ‘μ λμλ, νμ ν° λμ λΆν° μ΄μ©νλ κ²μ΄ μ’μμ μ μ μμ΅λλ€.
μ΄μ²λΌ νμ¬ μν©μμ μ΅μ μ΄λ€ μΆμ κ²μ κ³μ λ°λ³΅νλ μκ³ λ¦¬μ¦μ 그리λ μκ³ λ¦¬μ¦, μμ¬μμ΄ κΈ°λ²μ΄λΌ λΆλ¦ λλ€.
μ΄λ¬ν greedy μκ³ λ¦¬μ¦μ΄ μ£Όμ΄μ§ λμ λΌλ¦¬ λ°°μκ΄κ³μ λμ¬μλ λ¬Έμ μμλ μ€μ μ΅μ μ λ΅μ κ°μ Έμμ£Όκ² λ©λλ€.
greedy μκ³ λ¦¬μ¦μ λΉλ‘ λ§μ λ¬Έμ μ λν΄ μ΅μ μ λ΅μ κ°μ Έμ μ£Όμ§λ λͺ»νμ§λ§, κ·Έ λ°©λ²μ΄ κ΅μ₯ν κ°λ¨νκΈ° λλ¬Έμ μ΅μ μ λ΅μ ꡬνκΈ° νλ 볡μ‘ν λ¬Έμ μ λν΄ μ€μ λ΅μ κ·Όμ¬ν κ²°κ³Όλ₯Ό λΉ λ₯΄κ³ κ°κ²°νκ² κ΅¬νκ³ μΆμ λ μμ£Ό μ¬μ©λκΈ°λ ν©λλ€.
μ°μ΅λ¬Έμ : λμ λνκΈ°
μλ‘ λ€λ₯Έ λμ n μ’ λ₯λ‘ κΈμ‘ kλ₯Ό μμ±μν€κΈ° μν΄ νμν λμ κ°μμ μ΅μκ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμΈμ.
λ¨, 2λ²μ§ΈλΆν° μ£Όμ΄μ§λ λμ μ κ°μΉκ°μ νμ λ°λ‘ μ λμ μ κ°μΉμ λ°°μλ‘ μ£Όμ΄μ§λλ€.
μ λ ₯ νμ
첫 λ²μ§Έ μ€μ λμ μ μ’ λ₯ κ°μ nκ³Ό κΈμ‘ kκ° κ³΅λ°±μ μ¬μ΄μ λκ³ μ£Όμ΄μ§λλ€.
λ λ²μ§Έ μ€λΆν° nκ°μ μ€μ κ±Έμ³ κ° λμ μ κ°μΉκ° μμ λμ λΆν° ν° λμ κΉμ§ μμλλ‘ μ£Όμ΄μ§λλ€.
- 1 ≤ n ≤ 10
- 1 ≤ k ≤ 100,000,000
- 1 ≤ λμ μ κ°μΉ ≤ 1,000,000
λ¨, μ£Όμ΄μ§ λμ λ€λ‘ kμμ λ§λ€μ§ λͺ»νλ μ λ ₯μ μ£Όμ΄μ§μ§ μμ΅λλ€.
μΆλ ₯ νμ
첫 λ²μ§Έ μ€μ kμμ λ§λλλ° νμν λμ μ κ°μμ μ΅μκ°μ μΆλ ₯ν©λλ€.
λμ νμ΄
#include <iostream>
using namespace std;
int main() {
int n; int k;
int coin[11]={0,};
cin >> n >> k;
for(int i=0; i<n; ++i) cin >> coin[i];
int cnt=0; int i=1;
while(k!=0){
if(k >= coin[n-i]) {
k-=coin[n-i];
cnt ++;
}
else i++;
}
cout << cnt;
return 0;
}
νμ¬ μν©μμ μ΅μ μΈ κ²μ λ°λ³΅νλ μμ¬μμ΄!
κ·Όλ° λμ λ¬Έμ μμμ μμ¬μμ΄ κΈ°λ² μ‘°κ±΄μ μ€λ μ²μ μμλ€
λ°°μ κ΄κ³ κΈ°μ΅νκΈ°
'π μκ³ λ¦¬μ¦ > Code Tree' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[μ½λνΈλ¦¬] BFS νμ / λ€ λ°©ν₯ νμΆ κ°λ₯ μ¬λΆ νλ³νκΈ° (0) | 2023.02.22 |
---|---|
[μ½λνΈλ¦¬] μμ νμ / μ리 μ λ¨μλ‘ μν μ°μ΅λ¬Έμ (0) | 2023.02.22 |
[μ½λνΈλ¦¬] Backtracking - λ°±νΈλνΉ / μ¬κ· μ°μ΅λ¬Έμ (0) | 2023.02.21 |
[μ½λνΈλ¦¬] DFS / BFS (0) | 2023.02.21 |
[μ½λνΈλ¦¬] TreeSet μ°μ΅λ¬Έμ (0) | 2023.02.09 |