[실버4 ] BOJ 2839 설탕 배달

요구사항

상근이가 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

문제 분석

• 정확하게 N킬로그램 배달해야 한다.
• 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
• 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다.
• 문제에서 가능한 최대 시간복잡도 = On제곱 → 5000 ** 2 = 2500만 < 1억(시간 제한 1초)

손으로 풀기

1. 5kg 봉투의 개수를 최대에서부터 최소(0)까지 줄여가면서 해를 찾는 방식
2. 5kg 봉투를 최대로 사용
3. 남은 무게가 3의 배수인지 확인
4. 5kg 봉투 개수를 하나 줄이고 재시도 (반복)
5. 성공 시 즉시 종료, 모든 경우 시도 후 실패시 -1 리턴

Sudo Code

int N (첫째 줄에 입력되는 배달 해야 하는 킬로그램)
int count (상근이가 배달해야 하는 최소 개수)

for(5KG 봉투의 최대 개수가 0이 될떄까지) {
	N에서 5를 뺄 수 있을 떄까지 뺀다.
	count++

	if(남은 무게가 3의 배수인가) {
		남은 무게에서 3을 뺀다
		if(남은 무게가 0이라면) {
			count 출력
			break;
		}
		(그게 아니라면 다음 continue = 5KG의 최대 개수 -1하고 다시 반복 -> 위에 4번)
	}
}
return -1;

Code

import java.util.Scanner;

public class BOJ2839 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.close();

        int fiveBags = N/5; // N = 18 -> 3

        for(int minBags = fiveBags; minBags >=0; minBags--){
            int remaining = N - (minBags * 5);

            if(remaining % 3 ==0) {
                int threeBags = remaining / 3; // remaining = 3 -> 1
                System.out.println(minBags + threeBags);
                System.exit(0);
            }
        }
        System.out.println(-1);
    }
}