2839번 문제

문제

풀이

첫 번째 풀이

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    static class Data {
        int cur;
        int cnt;
        Data(int cur, int cnt) {
            this.cur = cur;
            this.cnt = cnt;
        }
    }
    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 result = -1;

        Queue<Data> queue = new ArrayDeque<>();
        queue.add(new Data(n,0));
        while(!queue.isEmpty()) {
            Data data = queue.poll();
            if(data.cur == 0 ) {
                result = data.cnt;
                break;
            } else if(data.cur > 0){
                queue.add(new Data(data.cur - 3,data.cnt+1));
                queue.add(new Data(data.cur - 5,data.cnt+1));
            } else if(data.cur < -(3+5)){
                break;
            }
        }

        bw.write(result+"");
        bw.flush();
        bw.close();
        br.close();
    }
}

1. bfs로 풀이
2. -3과 -5를 동시에 계속해서 해가면서 0이 되는 순간의 cnt를 반환

결과는 .. 메모리 초과가 떴다.
조금 더 효율적으로, 쉽게 풀라는 의미 ..

두 번째 시도

import java.io.*;

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 result = 0;
        while(n > 0) {
            if(n%5 == 0) {
                result += n/5;
                break;
            } else {
                n -= 3;
                result ++;
            }
            if(n < 0) {
                result = -1;
                break;
            }
        }

        bw.write(result+"");
        bw.flush();
        bw.close();
        br.close();
    }
}

1. 5로 나누어떨어진다면 가장 최소의 봉지를 사용하는 것이므로 처음으로 체크한다.
2. 5로 나누어 떨어지지 않는다면,
   2-1. 3으로 나누어 떨어지거나,
   2-2. 그 무엇으로도 나누어 떨어지지 않는 경우로 나뉜다.
3. 3으로 나누어 떨어진다고 하더라도 그것이 최소의 봉지를 사용하는 것은 아닐 수 있으므로 (ex. 18의 경우) 3씩 계속해서 빼가면서 확인해나간다.
   => 3의 배수를 뺀 뒤 5로 나누어 떨어진다면 5로 나눈 뒤 while문을 빠져나간다.
   => 정확하게 봉지에 담을 수 없는 경우, 계속해서 -3이 되어 결국 음수가 되고, result = -1이 된다.

---