문제풀이[dp] - 설탕 배달, 1로 만들기

백준 2839번 - 설탕 배달 

 

package codingTestPractice.baekjoon;

import java.util.Scanner;

//설탕배달 dp
public class sol2839 {

    public int getMinBags(int sugar){
        int minBags=0; //최소 봉지 수
        int maxFiveKgBags = sugar/5; //5킬로그램 봉지 최대 개수
        boolean isPossible=false; //배달 가능 여부

        for(int i=maxFiveKgBags;i>=0;i--){
            if((sugar-i*5)%3==0){
                minBags=i+(sugar-i*5)/3;
                isPossible=true;
                break;
            }
        }

        return isPossible ? minBags : -1;
    }
    public static void main(String[] args) {
        sol2839 s = new sol2839();
        Scanner sc = new Scanner(System.in);

        int sugar = sc.nextInt();
        System.out.println(s.getMinBags(sugar));
    }
}

 

1로 만들기

 

package codingTestPractice.baekjoon;

import java.util.Scanner;

public class sol1463 {

    static Integer[] dp;

    public int recur(int n){

        if(dp[n]==null){
            //6으로 나눠질 경우
            if(n%6==0){
                dp[n] = Math.min(recur(n - 1), Math.min(recur(n / 3), recur(n / 2))) + 1;
            }
            //3으로만 나눠지는 경우
            else if(n%3==0){
                dp[n] = Math.min(recur(n / 3), recur(n - 1)) + 1;
            }
            //2로만 나눠지는 경우
            else if(n%2==0){
                dp[n] = Math.min(recur(n / 2), recur(n - 1)) + 1;
            }
            //2와 3으로 나누어지지 않는 경우
            else{
                dp[n] = recur(n - 1) + 1;
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        sol1463 s = new sol1463();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        dp = new Integer[n+1];
        dp[0]=dp[1]=0;

        System.out.println(s.recur(n));

    }
}