[백준알고리즘-JAVA]2839번 풀이(설탕 배달)

안녕하세요

인포돈입니다.

백준 알고리즘 2839번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2839 (설탕 배달)

 

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

입력 예시

18

출력 예시

4

입력 예시

4

출력 예시

-1

 

입력 예시

6

출력 예시

2

입력 예시

9

출력 예시

3

입력 예시

11

출력 예시

3

성공코드

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 num = Integer.parseInt(br.readLine());
		
		int N = 0;
		
		while(true){
		if(num%5 == 0) {
			N += num/5;
			break;
		}
		
		num -= 3;
		N++;
		
		if(num < 0) {
			N = -1;
			break;
		}
	}
		System.out.println(N);
		}
		}

설탕 배달 알고리즘에서 중요한 점은 먼저 5kg으로부터 처리해야 된다는 점을 생각해야 합니다.

 

주어진 입력에 대해 알아보면 먼저 5kg부터 들어야 최소로 설탕 박스를 가져갈 수 있기 때문입니다.

 

알고리즘 흐름도를 간략히 설명하면 다음과 같다.

 

입력받기 -> 받은 입력 5kg로 박스로 채워본다. -> 5kg으로 딱 맞춰서 안 나눠질 시 3kg으로 맞추기 -> 만약에 딱 떨어지지 않을 시 -1을 출력한다. 

 

해당 흐름대로 따라간다. 여기서부터 STEP을 따라가면서 하나씩 파헤쳐봅시다.

---

STEP1 최솟값 구해보기

 

처음 들어온 입력을 우선 2가지로 나누어 볼 수 있다.

 

 1번 입력이 5로 딱 나누어 떨어지는 경우

if(num%5 == 0) {
			N += num/5;
			break;
		}

 2번 입력이 5로 떨어지지 않는 경우

num -= 3;
N++;

 

1번의 경우 그냥 5kg으로 딱 떨어지면 그 개수가 바로 최소한의 값이다.

 

2번의 경우 또 한 번 나누어질 수 있다.

 

2 - 1번 3kg을 하나 챙긴 후 다시 한번 1번 또는 2번으로 간다.

if(num < 0) {
			N = -1;
			break;
		}

이러한 루프를 계속해서 돌다가 주어진 입력이 음수가 될 시 반복하는 부분을 빠져나오면 된다.

 

---

*알고리즘에 대한 공부법

 

이러한 발상을 하기까지는 많은 고심이 필요합니다.

 

물론 한 번에 떠올리기는 쉽지 않을 것입니다.

 

저 또한 해당 문제를 풀이하기 위해서 조건문을 여러 개 사용하여 코드 길이가 많이 길어지기도 하고 원하는 답이 출력되지 않을 때도 있었습니다.

 

최대한 시도해 보는 것이 가장 좋은 알고리즘 공부법입니다.

(아직 이러한 알고리즘에서 막히는 분들은 제한시간을 30분 ~ 1시간 정도를 두어 풀지 못할 시 다른 사람의 풀이를 통해 힌트를 얻어 풀어보는 것이 좋습니다)

 

초보의 경우 많은 알고리즘을 풀어 다양한 풀이법을 익히는 게 중요하고 어느 정도 중급의 실력에 올랐을 때부터는 한 문제를 가지고 풀 때까지 고심하여 초보시절에 배웠었던 다양한 풀이법을 완전히 익혀보는 시간이 되어야 한다고 생각합니다.