[JAVA 알고리즘]BAEKJOON 24390번 또 전자레인지야?

또 전자레인지야?

---

문제 설명

잇창명의 집에는 오래된 전자레인지가 있다. 백준 온라인 저지에서 문제를 너무 많이 푼 잇창명은 문득 이런 궁금증이 생기기 시작했다.

버튼을 최소 몇 번 눌러야 조리시간 2분을 맞출 수 있을까?

잇창명의 전자레인지에는 다음과 같이 버튼이 4개 있고, 각 버튼을 누르면 다음과 같이 작동한다. 초기 상태에는 조리시간이 0초이고, 조리 중이 아니며, 조리시작 버튼을 눌러야 조리가 시작된다.

• 10초: 조리시간이 10초 늘어난다.
• 1분: 조리시간이 1분(60초) 늘어난다.
• 10분: 조리시간이 10분(600초) 늘어난다.
• 조리시작
  • 조리 중이 아닐 때: 조리가 시작된다. 만약에 조리시간이 0초였다면 30초로 늘어난다.
  • 조리 중일 때: 조리시간이 30초 늘어난다.
• 모든 버튼은 조리 중인지의 여부와 무관하게 항상 누를 수 있으며, 별도의 언급이 없을 경우 항상 같은 동작을 한다.

예를 들어 이 전자레인지로 2분을 맞추려면 조리시작 버튼을 4번 누르면 되지만, 최적의 방법은 아니다. 그 대신 1분-1분-조리시작 순서로 버튼을 누르면 버튼을 누른 횟수가 3번이 되어 최적이다. 1분-1분의 경우에는 조리가 되지 않기 때문에 최적이 아니다. 실제로는 조리 중에는 남은 조리시간이 계속 줄어들고 중간에 조리를 취소할 수 있지만, 이 문제에서는 생각하지 않기로 한다.

잇창명은 지난 한 학기 동안 전자레인지를 이용할 때마다 매번 문제로 내고 싶은 마음이 들어서 괴로워하고 있다. 잇창명을 도와주자!

입력

첫 줄에 잇창명이 원하는 조리시간이 M:S 형태로 주어진다(0 ≤ M ≤ 60, 0 ≤ S ≤ 59). M은 분, S는 초이며, 항상 두 자리 숫자로 주어진다.

조리시간은 10초 이상 60분(3600초) 이하이며, 항상 10의 배수이다.

출력

주어진 조리시간을 맞추기 위해 버튼을 눌러야 하는 최소 횟수를 출력한다.

제한사항

• 없음

입출력 예

input	return
02:00	3
추가 반례
00:00	0
00:40	2

---

문제 분석

시간이 증가하는 조건은 4가지다.

1. 10초 증가
2. 60초 증가
3. 600초 증가
4. 30초 증가 (시작)

30초 증가를 안 했으면 시작버튼이 안 눌렸으니 한 번 더 눌러줘야 한다.
조리 시간이 분 초로 주어지는데 계산을 편하게 할 수 있도록 초로 통일해 준다.
항상 주어진 목표가 0일 때를 까먹지 말자.

손으로 풀기

1. 계산하기 쉽게 10초를 기준으로 초를 계산해서 목표 시간을 계산한다.
2. BFS 방식을 사용한다.
   1. 현재 시간에 10초단위로 변경해서 반복해서 추가를 한다.
   2. 더해진 시간이 목표 시간보다 작거나 같고 사용한 적이 없으면 큐에 넣어준다.
   3. 넣어줄 때 더하는 초가 3으로 시작버튼인 경우 시작 버튼을 누른 것을 표시해서 넣어준다.
   4. 목표시간에 도달했을 때, 시작 버튼 유무를 확인해 눌리지 않았으면 횟수를 1 더하고 출력한다.
3. 목표시간이 0일 경우 버튼 횟수를 0으로 출력하고 아닐 경우, 횟수를 출력한다.

나의 문제풀이

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

public class Main {

    static boolean[] visited = new boolean[361];
    static int time;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        // 분과 초를 나눠 각각 10초단위를 기준으로 목표시간을 계산한다.
        String[] times = bufferedReader.readLine().split(":");
        int minute = Integer.parseInt(times[0]) * 6;
        int second = Integer.parseInt(times[1]) / 10;
        time = minute + second;

        int answer = BFS();

        // 시작 시간이 0 초이면 버튼을 누를 필요가 없다.
        System.out.println(time == 0 ? 0 : answer);
    }

    public static int BFS() {
        // 10초 단위로 시간을 계산한다.
        int[] button = {1, 3, 6, 60};

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 0});
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int currentTime = temp[0];
            int currentCnt = temp[1];
            int start = temp[2];

            // 시작 버튼이 눌렸으면 그대로 출력하고 안 눌렸다면, 눌러야할 시간이 있으면 시작 버튼의 횟수를 추가 한다.
            if (time == currentTime) {
                if (start == 1) return currentCnt;
                return currentCnt + 1;
            }

            for (int i = 0; i < 4; i++) {
                int nextTime = currentTime + button[i];

                if (nextTime <= time && !visited[nextTime]) {
                    visited[nextTime] = true;
                    if (button[i] == 3) { // 시작 버튼을 누르면 확인
                        queue.offer(new int[]{nextTime, currentCnt + 1, 1});
                    } else {
                        queue.offer(new int[]{nextTime, currentCnt + 1, start});
                    }
                }
            }
        }

        return 0;
    }
}

한동안 너무 DFS, BFS방식의 문제만 찾아서 풀다가 다른 방식의 문제를 좀 풀기 위해서 다이나믹 프로그래밍 문제를 찾아 풀었는데, 분석을 하다 보니 웬걸 또 BFS방식으로 풀리는 문제였다. 그래도 기존의 BFS들과는 조금은 다르게 생각해야 하는 부분들이 있어 재미있게 풀었다. 그리고 매번 목표에서 아무것도 진행 안 해도 되는 부분을 고려 안 해 매번 한 번씩 틀리는데 다음부터는 잘 생각해서 처음부터 조건을 잘 잡아줘야겠다.

---

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 그리디 알고리즘

문제 출처 - https://www.acmicpc.net/problem/24390

24390번: 또 전자레인지야?