[백준] 2839번 설탕 배달 JAVA (자바) 풀이

문제 2839번 

 :  설탕 N킬로그램 배달해야 한다
    설탕은 봉지에 담겨져 있다 ( 3킬로그램 봉지 or 5킬로그램 봉지 )
    봉지의 최소 개수를 구해라

 

[입력]

 :  첫 줄에 N

 

 

[출력]

 :  봉지의 최소 개수 출력

    ( 정확하게 N킬로그램 만들 수 없다면 -1 출력 )

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

1) Top-down(하향식)

     하위 문제를 재귀적으로 호출하여 해결함으로서 상위 문제를 해결하는 방식
     이 때 해결해놓은 하위 문제를 저장해 놓기 위해 Memoization사용

 

public class Topdown {
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		System.out.println(fibo(n));
		
	}
	
    // Top-down
	static int fibo(int x) {
		if( x ==1 || x==2) return 1;
		if(dp[x] != 0) return dp[x];
		dp[x] = fibo(x-1) + fibo(x-2);
		return dp[x];
	}
}

 

2) Bottom-up(상향식)

 

    하위에서부터 문제를 먼저 해결하고 얻어진 값들을 이용해서 상위 문제를 해결해나가는 방식

    반복문을 사용해서 구현하고 문제의 결과 값을 저장하는 리스트는 DP 테이블이라 부른다

    

public class Bottomup {

	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		
		System.out.println(fibo(n));
	}
	
    // Bottom-up
	static int fibo(int x) {
		dp[1] =1;
		dp[2] =1;
		for(int i=3; i<x+1; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[x];
	}

 

 

 

 [코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[N + 1];
        int INF = Integer.MAX_VALUE;

        Arrays.fill(dp, INF);

        if (N >= 3) dp[3] = 1;
        if (N >= 5) dp[5] = 1;

        for (int i = 6; i <= N; i++) {
            if (dp[i - 3] != INF || dp[i - 5] != INF) {  // 유효한 값을 가지고 있을 때만 갱신
                dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;
            }
        }

        System.out.println(dp[N] == INF ? -1 : dp[N]);
    }
}

 

 

 [해설]
     

 :  int N = Integer.parseInt(br.readLine());  첫째줄 입력 킬로그램

 

 :  int[] dp = new int[N + 1];  dp 설정 

    int INF = Integer.MAX_VALUE;  출력할 수 없는 킬로그램은 INF로 초기화

 

 :  Arrays.fill(dp, INF);  dp에 INF로 초기화
        
 :  if (N >= 3)  dp[3] = 1;  dp[3] = 3키로짜리 봉지 초기화
    if (N >= 5)  dp[5] = 1;  dp[5] = 5키로짜리 봉지 초기화

 

 :  for (int i = 6; i <= N; i++) {  5까지 값은 위에서 초기화 했으니까 6부터 시작
            if (dp[i - 3] != INF || dp[i - 5] != INF) {  하나라도 유효할 경우만 갱신
                dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;  최소값 구하고 바로 1 count
            }
    }

    

 :  System.out.println(dp[n]==INF?-1:dp[n]);  INF면 -1로 출력하고 아니면 dp[n] 바로 출력

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *