[JAVA] 백준 2839번 - 설탕 배달

 

 

 

<코드>

import java.util.*;
public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int dp[] = new int[5001];
		
		dp[0] = 0;
		dp[1] = -1;
		dp[2] = -1;
		dp[3] = 1;
		dp[4] = -1;
		
		for (int i = 5; i <= N; i++) {

			if(dp[i-3] == -1 && dp[i-5] == -1) {
				dp[i] = -1;
			} else {
				if(Math.min(dp[i-3], dp[i-5]) == -1) {
					dp[i] = Math.max(dp[i-3], dp[i-5]) + 1;
				}else {
					dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
				}
			}
		}
		System.out.println(dp[N]);

	}
}

 

풀이 방법

dp로 n을 증가시키면서 각 kg마다 최소의 개수 저장 

			if(dp[i-3] == -1 && dp[i-5] == -1) {
				dp[i] = -1;
			} else {
				if(Math.min(dp[i-3], dp[i-5]) == -1) {
					dp[i] = Math.max(dp[i-3], dp[i-5]) + 1;
				}else {
					dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
				}
			}

만약 (i-3) kg과 (i-5) kg를 만들 방법이 없다면(-1)

i kg 또한 만들 수 없습니다.

기본 점화식은 dp[i] = min(dp[i-3], dp[i-5]) + 1이며,

만약 dp[i-3]과 dp[i-5]중 하나가 -1이라면 -1이 아닌 dp값에서 1을 더한 값이 i kg그램을 만드는데 필요한 최소의 개수가 됩니다.

 

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달