[Baekjoon 4307] 개미 - JAVA

[Silver I] 개미 - 4307

문제 링크

성능 요약

메모리: 47540 KB, 시간: 436 ms

분류

애드 혹

문제 설명

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 나타낸다. 입력으로 주어지는 모든 수는 1,000,000보다 작거나 같으며, 공백으로 구분되어져 있다. 개미의 위치는 막대 왼쪽 끝에서부터 떨어진 거리이다.

출력

각 테스트 케이스에 대해서, 두 숫자를 출력한다. 첫 번째 숫자는 개미가 모두 땅으로 떨어지는 가능한 시간 중 가장 빠른 시간, 두 번째 숫자는 가장 늦은 시간이다.

문제 풀이

• 개미들의 속도는 모두 1cm/s다.
• 개미가 막대의 끝에 도달하면 즉시 떨어진다.
• 두 개미가 서로 만나게 된다면, 방향을 반대로 바꾸어 걸어간다.

처음에는 개미가 만나면 방향을 바꾸는걸 어떻게 하지 고민했었는데 다시 생각해보니 개미가 만나는걸 고려할 필요가 없었다.

개미1										개미2
1	2	3	4	5	6	7	8	9	10	11

여기서 개미1이 가장 늦게 떨어지는 시간은 우측으로 이동해서 떨어지는 경우가 된다.

이는 10초가 걸린다.

만약에 개미1과 개미2가 서로를 향해 다가갈 경우를 생각해보자

					만나는 지점
1	2	3	4	5	6	7	8	9	10	11

위와 같이 서로 만날 경우 5초가 걸리고 직후 방향을 바꿔서 이동한다.

개미1										개미2
1	2	3	4	5	6	7	8	9	10	11

방향을 바꾼뒤 5초간 더 이동한 뒤 떨어진다.

즉, 서로 만날 경우에도 최대 시간이 동일하게 5초가 걸린다.

때문에, 문제에서 주어진 방향을 바꾼다는 고려하지 않아도 된다는 결론이 나와서 개미들의 최솟값과, 최댓값을 구해서 그대로 출력만 해주면 된다.

필자는 Math를 사용해서 문제를 풀었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

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

            int[] antPositions = new int[antCnt];

            int minTimeToFall = Integer.MIN_VALUE;
            int maxTimeToFall = Integer.MIN_VALUE;

            for (int j = 0; j < antCnt; j++) {
                st = new StringTokenizer(br.readLine());
                int antPosition = Integer.parseInt(st.nextToken());

                int timeToReachMin = Math.min(antPosition, stickLength - antPosition);
                int timeToReachMax = Math.max(antPosition, stickLength - antPosition);

                minTimeToFall = Math.max(minTimeToFall, timeToReachMin);
                maxTimeToFall = Math.max(maxTimeToFall, timeToReachMax);
            }
            bw.write(minTimeToFall + " " + maxTimeToFall + "\n");
        }

        bw.flush();
        bw.close();
    }
}

코드 풀이

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

• n: 테스트 케이스를 저장할 변수

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

            int[] antPositions = new int[antCnt];

            int minTimeToFall = Integer.MIN_VALUE;
            int maxTimeToFall = Integer.MIN_VALUE;

• stickLength: 각 테스트 케이스의 막대기 길이를 나타내는 변수
• antCnt: 각 테스트 케이스 내 개미의 수를 나타내는 변수
• antPositions: 각 테스트 케이스 내 개미의 위치를 저장하는 배열
• minTimeToFall: 테스트 케이스 내 개미들 중에서 가장 늦게 떨어지는 시간을 나타내는 변수
• maxTimeToFall: 테스트 케이스 내 개미들 중에서 가장 빨리 떨어지는 시간을 나타내는 변수

            for (int j = 0; j < antCnt; j++) {
                st = new StringTokenizer(br.readLine());
                int antPosition = Integer.parseInt(st.nextToken());

                int timeToReachMin = Math.min(antPosition, stickLength - antPosition);
                int timeToReachMax = Math.max(antPosition, stickLength - antPosition);

                minTimeToFall = Math.max(minTimeToFall, timeToReachMin);
                maxTimeToFall = Math.max(maxTimeToFall, timeToReachMax);
            }

• antPosition: 개미의 위치를 나타내는 변수
• timeToReachMin: 개미가 막대기의 한쪽 끝에 가까울 때 떨어지는 시간을 나타내는 변수
• timeToReachMax: 개미가 막대기의 중심에 가까울 때 떨어지는 시간을 나타내는 변수

            bw.write(minTimeToFall + " " + maxTimeToFall + "\n");
        }

        bw.flush();
        bw.close();
    }
}

• bw를 사용해서 구한 최소시간과 최대시간을 출력했다.