Baekjoon 문제 풀기 (2839번 : 설탕 배달) Java

2839번 : 설탕 배달

1. 문제읽기

---

그리디 알고리즘

2. 제출 코드

---

if문이 너무 많아졌다.. 틀리기도 했지만 직감적으로 이렇게 풀면 안되겠다라고 생각하긴 했다 ㅋㅋㅋ
테스트 케이스 주어진 건 다 통과했는데, 계속 반례가 나와 if문을 추가하다보니 이상해졌다..

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        // 5를 빼고 5, 3으로 나눠 떨어지는지 확인
        int target = n;
        int count = 0;
        boolean flag = false;  // 나눠서 안떨어지는 수
        while(target > 0) {
            target -= 5;
            count ++;
            if(target < 0) {
                break;
            }
            if(target == 0) {
                System.out.println(count);
                flag = true;
                break;
            }
            if(target%5 == 0) {
                count += target/5;
                System.out.println(count);
                flag = true;
                break;
            }
            if(target%3 == 0) {
                count += target/3;
                System.out.println(count);
                flag = true;
                break;
            }
        }
        if(!flag) {  // 나눠서 안떨어질때
            if(n%3==0) {  // 3으로 나눠 떨어진다면
                System.out.println(n/3);
            } else {
                System.out.println(-1);
            }
        }
    }
}

3. 공부할 것

---

로직은 비슷했지만 생각을 잘못했다.
그리디 알고리즘이기 때문에 5를 계속 빼줘야한다고 생각했다. 5가 가장 큰 단위였기 때문이다.
그러나 3을 계속 빼주면서 5의 배수일 때를 고려해야했다.
경우의 수가 아래 4가지이기 때문이다.

1. 5의 배수인 경우 ex) 5, 10
2. 5a + 3b인 경우 ex) 13, 18
3. 3의 배수인 경우 ex) 6, 12
4. 만들 수 없는 경우 ex) 4, 7

아래 코드는 위 모든 경우의 수를 만족한다.

1. 첫번째 if문으로 빠져나감
2. 3을 계속 빼주다가 첫번째 if문으로 빠져나감
3. while문이 계속 반복되다가 n이 0이 되면 첫번째 if문으로 빠져나감
4. while문이 계속 반복되다가 n이 음수가 되면 -1 출력

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

public class BOJ2839 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int count = 0;
        while(true) {
            if(n%5==0) {  
                count += n/5;
                System.out.println(count);
                break;
            } else {  
                n -= 3;
                count++;
            }
            if(n<0) {  
                System.out.println(-1);
                break;
            }
        }
    }
}