백준 2839번 - 설탕 배달

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

2839번: 설탕 배달

 

 

 

 

 

예전에 풀었던 문제이다. 하지만 풀이가 생각이 잘 나지 않았다..

DP로 풀어야 하나 생각했는데, 더 간단한 풀이가 있다.

 

 

 

 

1. 처음에 5로 나눠떨어지면 5로 나누고 정답을 도출하고 끝낸다.

2. 하지만 처음부터 5로 나눠떨어지는 수가 아니라면 5로 나눠떨어질때까지 3을 뺀다.

3. 계속 3씩 빼다가 0이하로 떨어지면 결국 불가능한 것이다.

 

 

 

 

 

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int count = 0;
		while(true) {
			if(N % 5 == 0 ) { //5로 나눠떨어지는 경우
				count += N / 5;
				break;
			} else { //5로 안나눠떨어지는 경우
				count++;
				N -= 3; //3씩 계속 뺌(나누기)
			}
			
			if(N < 0) { //불가능
				count = -1;
				break;
			}
		}
		
		System.out.println(count);
	}

}

 

 

 

 

 

결과

 

이전이랑 똑같은 풀이인데 시간이 100ms대에서 200ms대로 늘었다. 스캐너로 입력을 받아서 그런 것 같다..