백준 2839번 : 설탕 배달 자바

 

 

 

🧫 문제 분석

 

✔️ 출처

설탕 배달 실버 4

 

📖 문제

 

풀었던 문제를 보다가 꼭 다시 풀라고 메모를 적어놔서 다시 풀었다. 

DP로 풀 수 있는 문제이다. 

3 과 5로 나눠 떨어지지 않는 1 , 2, 4, 7 은 -1로 

3 5 은 1로 미리 초기화한다.

6도 미리 2로 초기화한다.

 

N - 3과 N - 5 중 더 작은 값을 취하고 +1해주면 dp[N] 이 된다. 

 

N에서 3키로를 한 봉지를 담고 [N-3] 키로일때 얻은 봉지 최솟값과

N에서 5키로를 한 봉지를 담고 [N-5] 키로일때 얻은 봉지 최솟값 중 더 작은 값을 취하는 것이다.

 

dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;

 

 

 

 

 

 

 

---

🔅 문제 풀이

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(br.readLine());
        int[] dp = new int[5001];
        dp[1] = dp[2] = dp[4] = dp[7] = -1;
        dp[3] = dp[5] = 1;
        dp[6] = 2;

		// 최솟 값을 찾아야하기에 -1인 값들은 잠시 100으로 높여놓는다. 
        if (num > 7) {
            dp[1] = dp[2] = dp[4] = dp[7]= 100;
        }

        for (int i = 8; i <= num; i++) {

            dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;
        }

        bw.write(dp[num]+ "");
        bw.flush();
        bw.close();
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  예외 상황 (여기서는 7) 을 잘 찾아서 처리해주자.