[2839] 설탕 배달

[Java]

문제 링크: https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

[문제]

1. 배달 업무를 하는 상근이가 근무하는 설탕공장에는 5kg 봉지설탕과 3kg 봉지설탕이 있습니다.
2. 입력 값으로 N(3≤N≤5000)을 받았을 때, 상근이는 최소 몇 봉지를 옮겨야하는지 출력하십시오.
   (단, 정확하게 3kg과 5kg의 봉지설탕으로 N킬로그램을 만들 수 없는 경우에는 -1을 출력합니다.)

 

[코드]

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

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 N = Integer.parseInt(br.readLine());
		int cnt = 0;
		
		if(N%5==0) {
			cnt = N/5;
			N%=5;
		}
		else {
			if(N>=3) {
				while(N>=3) {
					cnt++;
					N-=3;
					if(N%5==0) {
						cnt+=(N/5);
						N%=5;
					}
				}
			}
		}
		if(N==0)
			bw.write(String.valueOf(cnt));
		else
			bw.write(String.valueOf(-1));
		bw.close();
		br.close();
	}
}

 

[풀이]

1. N: 주문들어온 설탕의 kg
2. cnt: 봉지설탕의 개수
3. N이 5로 나누어 떨어질 경우 cnt에 몫을 추가, N은 0으로 수정(마지막에 N이 0이 아닌 경우에는 -1을 출력할 예정)
4. 5로 나누어 떨어지지 않고 N이 3보다 클 때, 가장 작은 수인 3부터 하나씩 빼주며 N은 3씩 감소, cnt는 1씩 증가시킵니다.
5. 4번이 한 번씩 진행될 때마다 3번을 진행합니다.
6. 최종적으로 N이 3보다 작을 때, -1 출력 | N이 0일 때, cnt를 출력

5부터 1씩 빼면서 하면 안되나요? 할 수 있지만, 입력된 수가 6인 경우 -1이 출력되게 됩니다. 해당 문제는 DP의 기초 문제라 생각하며, 처음 접할 경우 발생이 어려울 수 있으나 익숙해지시면 어렵지 않은 문제라고 생각합니다.