[실버 4] 2839. 설탕 배달 / DP (Java)

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

2839번: 설탕 배달

쇠주 배달 시급

---

※  문제를 요약하면 아래와 같습니다.

▶ 상근 씨가 N 킬로그램의 설탕을 배달

▶ 봉지는 3kg, 5kg 두가지의 종류가 존재

▶ 상근씨는 최대한 적은 봉지를 사용하고 싶음

▶ 입력으로 설탕 N kg의 값이 주어짐

▶ 최소로 사용한 봉지 수 출력, 정확하게 N kg을 만들 수 없다면 -1 출력 

---

◈ Input - 1

18

◈ Output - 1 ( 3 + 5 + 5 + 5 )

4

◈ Input - 2

4

◈ Output - 2 ( 3 or 5로 구성할 수 없음 )

-1

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ https://heih.tistory.com/40 풀이를 DP로 변경하여 풀이

    1. 5로 나누어 떨어질 경우 DP 배열에서 현재 인덱스 -5 배열의 값에 1을 더하여 저장

    2. 1번의 경우가 아니고, 3으로 나누어 떨어질 경우 DP 배열에서 현재 인덱스 -3 배열의 값에 1을 더하여 저장

    3. 1,2번의 경우가 아니고, i가 5보다 크며 현재 인덱스-3번째의 dp값이 0이 아닐경우,

       현재 인덱스의 -3번째 배열과 -5번째 배열의 dp값이 일치하면 해당 dp값에 1을 더하여 현재 인덱스에 저장

    4. 입력된 N의 값이 0일 경우 -1 출력

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
    // TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(bReader.readLine());

		int[] narrDP = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			if (i % 5 == 0)
				narrDP[i] = narrDP[i - 5] + 1;
			else if (i % 3 == 0)
				narrDP[i] = narrDP[i - 3] + 1;
			else if (i >= 5 && narrDP[i - 3] != 0 && narrDP[i - 3] == narrDP[i - 5])
				narrDP[i] = narrDP[i - 3] + 1;
		}

		if (narrDP[N] == 0)
			bWriter.write("-1");
		else
			bWriter.write(String.valueOf(narrDP[N]));

		bWriter.close();

	}
}

---

Good Luck! (피드백 감사합니다!)