λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

πŸ“ μ•Œκ³ λ¦¬μ¦˜/Code Tree

[μ½”λ“œνŠΈλ¦¬] Greedy - 그리디 μ•Œκ³ λ¦¬μ¦˜ / 동전 μ—°μŠ΅λ¬Έμ œ

728x90

 

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;
}

 

ν˜„μž¬ μƒν™©μ—μ„œ μ΅œμ„ μΈ 것을 λ°˜λ³΅ν•˜λŠ” μš•μ‹¬μŸμ΄!

근데 동전 λ¬Έμ œμ—μ„œμ˜ μš•μ‹¬μŸμ΄ 기법 쑰건은 였늘 처음 μ•Œμ•˜λ‹€

배수 관계 κΈ°μ–΅ν•˜κΈ°

 

728x90