백준 2839번 설탕 배달(JAVA,DP)

<풀이방식>

직관적인 방식으로 풀지않고 DP로 풀려고 노력했다. 먼저 target은 배달해야하는 설탕의 양, dp[] 은 해당 target에서 필요한 최소 봉지의 수를 담는 배열로 설정했다.

먼저 dp[3] = 1, dp[5] = 1 을 설정.

• target =15 같은 경우는 5와 3모두 나눠지지만 5로 나눠야 봉지가 최소이므로 5먼저 나누고 dp[i] = dp[i-5] +1;
• 3으로 나눠지는 경우는 dp[i] = dp[i-3] +1;
• 3,5로 모두 안나눠지는 수의 경우는 dp[i-3] , dp[i-5]를 확인해서 전부 0이면 정확히 배달 불가능한 경우이며 둘중 하나라도 0이 아니라면 그 숫자에 1을 더하면 배달이 가능하다.
  둘다 0이 아니라면 최소값에 1을 더해주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	public static void main(String[] args ) throws IOException{
		Scanner sc = new Scanner(System.in);

		int target = sc.nextInt();
		int [] dp = new int[target+1];//봉지 몇개 필요한지 담는 배열
		Arrays.fill(dp,0);

		if(target >= 3)
			dp[3] = 1;
		if(target >= 5) {
			dp[5] = 1;
			for(int i = 6 ; i < dp.length; i++) {

				if(i%5 ==0) { //5랑 3이랑 다 나눠지면 5가 먼저 체크되어야 최소값이됨
					dp[i] = dp[i-5] +1;
				}
				else if (i %3 ==0 )
					dp[i] = dp[i-3] +1;
				//5나 3으로 모두 안나눠지는 숫자
				else {
					if(dp[i-5] ==0 && dp[i-3] ==0)
						dp[i] = -1;
					else if(dp[i-5] ==0 && dp[i-3] !=0)
						dp[i] = dp[i-3]+1;
					else if(dp[i-5] !=0 && dp[i-3] ==0)
						dp[i] = dp[i-5] +1;
					else if(dp[i-5] !=0 && dp[i-3] != 0){
						dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
					}
				}
			}
		}
		if(dp[target] > 0)
			System.out.printf("%d", dp[target]);
		else System.out.println(-1);

	}
}