[알고리즘] 그리디 문제 풀이

백준 2839

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result =0;
        while(true){
            if(n%5==0){
                result+=n/5;
                System.out.print(result);
                break;
            }else{
                n-=3;
                result+=1;
            }   
            if(n<0){
            System.out.print("-1");
            break;
            }
        } 
    }
}

얻어갈 점:

• 처음 문제 풀이할 때 가능한 적은 봉지를 들고가려면, 3kg와 5kg 봉지중 5kg를 최대한 많이 써야하기 때문에 입력값을 5로 나누고 나머지를 3kg로 채우려고 했다. 그러나 이러한 풀이는 9kg같이 3kg를 3개 이용하는 것이 불가능했다.
• idea는 최대한 적은 봉지를 드는 것 => 5kg를 최대한 많이 사용하는 것 => 3kg를 최대한 덜 사용하는 것 => 3kg를 0부터 1개씩 늘리면서 입력값에 -3하면서 5로 나누려고 해보자!
• while문에 true로 조건을 걸고 , 안에서 특정 조건을 만족했을때 break
• 9kg같이 3kg 3번하면 0되는데 if(n==0)/출력/break 해야하지않나? => if(n%5==0) 조건에서 n이 0이면 n%5==0도 만족하기 때문에 출력과 break 실행됨