본문 바로가기

알고리즘 문제 풀이

<알고리즘 Q2 - Greedy> 편의점 알바 // 노가다성 && 배열

 

 

==============해답===============

 

public class Solution { 
  public int partTimeJob(int k) {
    // TODO:
    /*
    금액 k 의 1원, 5원, 10원, 50원, 100원, 500원 동전의 최소 갯수
    <풀이방법>
    1. 주어진 금액 k에 큰 동전 단위로 먼저 나누고 남은 금액을 다음 단위로 나누며 쪼갠다.
    500, 100, 50, 10, 5, 1
    */
 
    // 1. k금액 / 500원 으로 500원의 최댓값.
    int fiveHundred = k/500;

    // 2. (k금액 -  (500원으로 나눈 값 *500원)) / 100
    int aHundred = (k - (fiveHundred*500))/100;
    
    // 3. (k금액 - (500원으로 나눈 값*500) + (100원으로 나눈값 * 100) ) / 50
    int fifty = (k - ((fiveHundred*500)+(aHundred*100)))/50;
    
    // 4. (k금액 - (500원으로 나눈 값*500) + (100원으로 나눈값 * 100) + (50원으로 나눈값 * 50) ) / 10
    int ten = (k - (((fiveHundred*500)+(aHundred*100)+(fifty*50))))/10;
    
    // 5. (k금액 - (500원으로 나눈값*500) + (100원으로 나눈값 * 100)+(50원으로 나눈값 *50)+ (10원으로 나눈값*10))/5
    int five = (k - (((fiveHundred*500)+(aHundred*100)+(fifty*50)+(ten*10))))/5;
    
    int one = (k - ((((fiveHundred*500)+(aHundred*100)+(fifty*50)+(ten*10)+(five*5)))))/1;

    int coins = fiveHundred+aHundred+fifty+ten+five+one;
    return coins;

  } 
}

================== 배열을 활용한 정답 ==================

 

int[] wallet = {500, 100, 50, 10, 5, 1};
int k = 8762;
int coins = 0;
int result = 0;

for (int i = 0; i < wallet.length; i++) {
    coins = k/wallet[i];
    result = result + coins;
    k = k - (coins * wallet[i]);
}
System.out.println(result);