[백준] 4307번. 개미(JAVA)

문제

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

---

풀이(40분)

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

public class Main {
    public static int testCase; // 테스트 수
    public static int n;  // 개미의 수
    public static int l;  // 막대의 길이
    public static int[] arr; // 각 개미의 시작 위치를 저장하는 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 표준 입력으로부터 입력을 받음
        StringTokenizer st = new StringTokenizer(br.readLine()); // 첫 번째 줄에서 테스트 케이스 수를 읽음

        testCase = Integer.parseInt(st.nextToken());
        for (int i = 0; i < testCase; i++) {
            st = new StringTokenizer(br.readLine());
            l = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());

            arr = new int[n];
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine()); // 각 개미의 시작 위치
                arr[j] = Integer.parseInt(st.nextToken());
            }
            int[] answer = sol();
            System.out.println(answer[0] + " " + answer[1]);
        }
    }

    public static int[] sol() {
        int minTime = 0; // 모든 개미에 대한 최소 시간
        int maxTime = 0; // 모든 개미에 대한 최대 시간

        for (int i = 0; i < n; i++) {
            int minTmpTime = Math.min(arr[i], l - arr[i]); // 한 개미의 최소 시간
            int maxTmpTime = Math.max(arr[i], l - arr[i]); // 한 개미의 최대 시간

            minTime = Math.max(minTmpTime, minTime); // 모든 개미에 대한 최소 시간 업데이트
            maxTime = Math.max(maxTmpTime, maxTime); // 모든 개미에 대한 최대 시간 업데이트
        }
        return new int[]{minTime, maxTime};
    }
}

 

---

문제 풀이 전략

 

사실 아직까지 정확히 다른 케이스가 있지 않을까 고민이 되는 문제이다.

-> 완벽하게 합리적인 근거를 만들어서 납득하지는 못했다.

 

문제 풀이는 다음과 같다.

1. 각 개미에 대한 양쪽으로의 추락 시간을 구한다.(여기서 각 개미에 대한 최대와 최소의 시간이 나온다.)

2. 1번에서 구한 값 중 최소 중의 최대와, 최대 중의 최대를 출력한다.

 

이것이 풀이의 전부이다. 내가 고민한 부분은 만약 어떠한 경우 두 개미가 더 끝에서 오는 개미와 계속 마주치며 중간에서 왔다 갔다를 반복하게 된다면 어떻게 될까?라는 것이다.

하지만 이 부분에 대한 고민은 더욱 해봐야겠지만 해결하기는 하였다.

만약, 정확한 근거가 생각난다면 추후에 작성해야겠다.