백준 - 2839 설탕배달

 

---

풀이 방법

스터디에서 곧 풀게될 문제라서 미리 풀어보았던 문제였다.

그런데 그리디 알고리즘이라는 것을 알고 한번 좌절ㅠㅠ 하였다가 몇번이나 틀리고 코드를 완성시켰다.

 

문제를 풀고나서 보니까 이게 나처럼 무식하게 풀 필요가 없이...규칙을 찾아서 풀면 풀리는 문제라는 것을 알고 한번 더 좌절했다ㅠㅠ

 

나는 PriorityQueue 와 BFS 를 사용해서 풀었다. 

 

queue 에 넣는 값에는 sum 과 cnt 를 사용하였다. cnt 는 n-5 또는 n-3 했을 때 각각 cnt+1 이 되도록 했고, sum 은 n-5 또는 n-3 된 값을 넣어두었다(사실 변수명이 sum 말고 minus 로 설정해야될 것이다). 이후 sum 과 cnt 를 queue에 넣어서 보다 작은 sum 값이 먼저 나오도록 만든다.

이를 통해서 sum == 0 에 도달한다면 5 와 3 으로 조합이 가능한 것임으로 도달했을 때 cnt 를 return 하고, 아닌 경우 -1 을 return 한다.

 

보다 자세한 내용은 코드 주석 참고!!

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;

// https://www.acmicpc.net/problem/2839
public class Quiz_2839 {
    static int n;
    
    // n 에 도달하지 못하는 경우 -1 임으로 기본값 -1로 초기화
    static int min = -1;
    
    // PriorityQueue 를 사용해서 가장 작은 값이 먼저 나오도록 -> 오름차순으로 나오도록
    static Queue<Sugar> q = new PriorityQueue<>((o1, o2)->{
        return o1.sum - o2.sum;
    });

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        // BFS 시작
        useBFS();

        System.out.println(min);
    }

    // 0 -> n 까지가는 방식이 아니라 n -> 0 까지 가는 방식으로 구현하였다.
    // n 에서 -5 나 -3 했을 때 0에 도달한다면 3과 5로 조합 가능함으로 cnt 를 return 하고,
    // n 에 도달할 수 없다면 -> 0 보다 작은 숫자가 나온다면 continue 해서 queue 가 계속 돌게 만들었다.
    
    // 문제는 맞았는데...아무래도 그리디 문제인지라 BFS 로 풀면 효율이 별로 좋지 못하다는 문제가 있다.
    // 만약 규칙을 찾아서 풀었다면 그게 훨씬 더 좋은 방법이다
    static void useBFS(){
        q.offer(new Sugar(n, 0));

        while (!q.isEmpty()) {
            Sugar su = q.poll();
            int sum = su.sum;
            int cnt = su.cnt;
            
            if(sum < 0){
                continue;
            } else if (sum == 0) {
                min = cnt;
                return;
            }else{
                q.offer(new Sugar(sum-3, cnt+1));
                q.offer(new Sugar(sum-5, cnt+1));
            }
        }
    }
}

class Sugar{
    int sum;
    int cnt;

    Sugar(int sum, int cnt) {
        this.sum = sum;
        this.cnt = cnt;
    }
}