[Java] 백준 2839번 : 설탕 배달

문제소개

 

해결과정

DP를 활용해 풀이했다.

문제풀이의 포인트는 낮은 무게부터 목표 무게까지 올라가면서, 3kg 혹은 5kg의 설탕봉지를 추가하면서 최솟값을 찾는 것과

목표 무게를 정확히 맞추는 것이 불가능일 수 있기 때문에, 무게를 맞출 수 있는 상황에만 설탕봉지를 추가해주는 것 두 가지이다.

 

무게를 맞출 수 없는 상황이라면 해당 dp 배열에는 0 값을 가지도록 만들었다.

따라서 3kg전에 값이 있는 경우와 없는 경우, 5kg전에 값이 있는 경우와 없는 경우를 적절히 조건으로 나눠 dp배열을 완성하면 된다.

 

솔루션

package DP.백준2839_설탕배달;

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


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];


        for (int i = 3; i < N + 1; i++) {
            if(i == 3) dp[i] = 1;
            if(i == 5) dp[i] = 1;
            try {
                if (dp[i - 3] == 0 && dp[i - 5] != 0) {
                    dp[i] = dp[i - 5] + 1;
                } else if (dp[i - 3] != 0 && dp[i - 5] == 0) {
                    dp[i] = dp[i - 3] + 1;
                } else if (dp[i - 3] != 0 && dp[i - 5] != 0) {
                    dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;
                }
            } catch (ArrayIndexOutOfBoundsException e) {}
        }
        if (dp[N] != 0) {
            System.out.println(dp[N]);
        } else {
            System.out.println(-1);
        }
    }
}