[백준 2839번/JAVA] 설탕 배달

문제

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

2839번: 설탕 배달

풀이 1

설탕 봉지의 개수를 줄이기 위해서는 5kg짜리를 최대한 많이 담고, 남은 무게를 3kg으로 채워야 한다.
먼저 N이 5의 배수이면 무조건 5kg짜리로 채운다. ans = N/5
N이 5의 배수가 아니면 우선 5kg짜리가 최대한으로 포함될 수 있도록 만든 후, 반복문으로 5kg의 개수를 줄여가며 남은 무게가 3kg으로 나누어떨어지는지 확인한다. ans = i + ( N - (5*i) / 3)
(여기까지 5kg짜리가 하나라도 포함될 수 있는지 확인 완료)
위의 어떤 경우에도 해당되지 않으면 (ans가 여전히 0이면) 마지막으로 3의 배수에 해당되는지 확인하고 해당되면 ans = N/3
해당되지 않으면 어떤 방식으로도 표현하지 못한다는 뜻이므로 ans = -1

코드 1

import java.io.*;
import java.util.*;

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 ans = 0;

        if(N % 5 == 0){
            ans = N/5;
        }else{
            for(int i=N/5; i>0; i--){
                int tmp = N - (5*i);
                if(tmp % 3 == 0) {
                    ans = i + (tmp / 3);
                    break;
                }
            }

            if(ans == 0){
                if(N % 3 == 0){
                    ans = N/3;
                }else ans = -1;
            }
        }

        bw.write(ans+" ");
        bw.close();
    }
}

풀이 2

풀이 1보다 훨씬 쉽고 간단하게 구현함

아래 내용을 무한반복
먼저 5의 배수이면 ans = N/5, 반복문 탈출
5의 배수가 아니면 3kg짜리 봉지를 하나 취한 후 ans++, N -= 3;
나머지 무게가 5의 배수인지 다시 확인
-> N==0이 되면 첫 번째 조건문에 걸려 반복문 탈출
-> N이 음수가 되면 3의 배수에도 해당되지 않는다는 의미이므로 ans = -1, 반복문 탈출

코드 2

import java.io.*;
import java.util.*;

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 ans = 0;

        while(true){
            if(N % 5 == 0){
                ans += N/5;
                break;
            }
            N -= 3;
            ans++;

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

        bw.write(ans+" ");
        bw.close();
    }
}

위-풀이1

아래-풀이2

 

Note

• 숫자의 규칙을 찾기 어려워서 반복문을 사용해 구현해보았다. (풀이1)
• 풀이2는 검색의 도움을 받았다. 항상 for문보다 while문의 성능이 떨어질 것이라고 생각했는데 아니라는 것을 깨달았다.
•  반복문은 입력값 범위가 커짐에 따라 성능이 떨어지지만, 숫자의 규칙을 찾아 조건문으로 구현할 경우 O(1)의 시간복잡도를 가지므로 입력값 범위와 상관없이 성능이 일정할 것이다. 구현은 쉬우나 설계가 어렵다. 다른 사람 설명을 들어도 어렵다..