백준 25196[자바] java 숲속에서 새 구경하기

 

문제 링크: https://www.acmicpc.net/problem/25196

25196번: 숲속에서 새 구경하기

 

▶문제

 

곰곰이는 바위에 앉아 새 3마리가 숲 주변을 비행하는 것을 구경하고 있다. 곰곰이는 새들을 관찰하면서 아래와 같은 사실들을 알아냈다.

• 첫 번째 새는 Av초, 두 번째 새는 Bv 초, 세 번째 새는 Cv 초 주기로 숲을 한 바퀴 돈다.
• 현재로부터 t (t≥0) 초가 지났다고 할 때, 곰곰이는...
  •  Av×ka+As≤t≤Av×ka+Ae일 때 첫 번째 새를 볼 수 있다. (ka는0 이상의 정수)
  •  Bv×kb+Bs≤t≤Bv×kb+Be 일 때 두 번째 새를 볼 수 있다. (kb는0 이상의 정수)
  •  Cv×kc+Cs≤t≤Cv×kc+Ce 일 때 세 번째 새를 볼 수 있다. (kc는0 이상의 정수)

곰곰 이가 새 3마리를 한 번에 볼 수 있는 최초의 시각은 현재로부터 몇 초 뒤인지 구해보자. 곰곰이는 바위에 앉아 새 3마리가 숲 주변을 비행하는 것을 구경하고 있다. 곰곰이는 새들을 관찰하면서 아래와 같은 사실들을 알아냈다.

• 첫 번째 새는 Av초, 두 번째 새는 Bv초, 세 번째 새는 Cv 초 주기로 숲을 한 바퀴 돈다.
• 현재로부터 t (t≥0) 초가 지났다고 할 때, 곰곰이는...
  •  Av×ka+As≤t≤Av×ka+Ae 일 때 첫 번째 새를 볼 수 있다. (ka는0 이상의 정수)
  •  Bv×kb+Bs≤t≤Bv×kb+Be 일 때 두 번째 새를 볼 수 있다. (kb는0 이상의 정수)
  •  Cv×kc+Cs≤t≤Cv×kc+Ce일 때 세 번째 새를 볼 수 있다. (kc는0 이상의 정수)

곰곰 이가 새 3마리를 한 번에 볼 수 있는 최초의 시각은 현재로부터 몇 초 뒤인지 구해보자.

• 첫 번째 새는 Av 초, 두 번째 새는 Bv 초, 세 번째 새는 Cv 초 주기로 숲을 한 바퀴 돈다.
• 현재로부터 t (t≥0) 초가 지났다고 할 때, 곰곰이는...
  •  Av×ka+As≤t≤Av×ka+Ae 일 때 첫 번째 새를 볼 수 있다. (ka는0 이상의 정수)
  •  Bv×kb+Bs≤t≤Bv×kb+Be일 때 두 번째 새를 볼 수 있다. (kb는 0 이상의 정수)
  •  Cv×kc+Cs≤t≤Cv×kc+Ce 일 때 세 번째 새를 볼 수 있다. (kc는 0 이상의 정수)

곰곰 이가 새 3마리를 한 번에 볼 수 있는 최초의 시각은 현재로부터 몇 초 뒤인지 구해보자.

 

▶입력

 

첫 번째 줄에 정수 Av, As, Ae 가 공백을 사이에 두고 주어진다. (1≤Av≤2000,0≤As≤Ae <Av)

두 번째 줄에 정수 Bv, Bs, Be가 공백을 사이에 두고 주어진다. (1≤Bv≤2000,0≤Bs≤Be <Bv)

세 번째 줄에 정수 Cv, Cs, Ce 가 공백을 사이에 두고 주어진다. (1≤Cv≤2000,0≤Cs≤Ce <Cv)

 

▶출력

 

현재로부터 t 초 뒤에 곰곰 이가 새 3마리를 최초로 한 번에 볼 수 있다고 할 때, t 를 첫 번째 줄에 출력하라.

만약 그런 순간이 영원히 오지 않는다면 -1 을 출력하라.

 

▶해설

 

푸는데 오래 걸린 문제입니다.. 수학적인 개념만 있다면 쉽게 풀 수 있습니다.

 

1. 반복되는 주기 구하기

 

새를 볼 수 있는 패턴이 같게 나오기 시작하는 시간대가 있습니다. 그것은 Av, Bv, Cv의 최소 공배수 시간입니다. 따라서 최소 공배수 시간까지 새들이 만나지 못했다면, 영원히 만나지 못합니다.

 

2. 시간을 얼마만큼 씩 증가시킬 것인가

 

세 수가 1999, 1997, 1993일 경우 약 70억이 넘어가는 큰 수입니다. 따라서 자료형은 0으로 해야 하고, 1씩 증가해서는 찾을 수 없습니다. 따라서 증가시킬 다른 기준점이 필요합니다. 

 

3. 시작점과 끝점에 주목하자. 

 

새를 볼 수 있는 A, B, C의 시작점과 끝점이 있습니다. 예제로 주어진 것을 보겠습니다. 

3 1 2
4 1 2
5 3 4

볼 수 있는 지점

A: 1~2

B: 1~2

C: 3~4

 

저희는 이 볼 수 있는 지점을 활용할 것입니다.

 

S = 3개의 시작 지점 중 가장 큰 것을 선택

E = 3개의 끝나는 지점 중 가장 작은 것을 선택

 

3개의 새들이 만나는 지점은 S <=E 일 경우입니다. 그 이유는 가장 큰 시작 지점이 가장 작은 끝나는 지점보다 작거나 같을 때 결국은 교차점이 생기기 때문입니다. 이때 S> E 일 경우에는 끝나는 지점이 가장 작은 것을 해당 주기만큼 증가시킵니다. 예제를 한 번 진행하겠습니다.

 

1차시 

S = 3, E = 2 X -> 끝나는 지점이 가장 작은 A, B 중에서 아무거나 주기만큼 증가 A: 4 ~ 5

 

2차시

S = 4, E = 2 X -> 끝나는 지점이 가장 작은 B를 주기 만큼 증가 B: 5 ~ 6

 

3차시

S=5, E= 4 X -> 끝나는 지점이 가장 작은 C를 주기만큼 증가 C: 8~9

 

~~

이렇게 진행했을 때 

S=13, E=13 O -> 가장 큰 스타트 지점인 S를 출력함으로써 끝내면 됩니다. 

 

long bound = arr[0][0]*arr[1][0]*arr[2][0]+1;
while(arr[0][2]<bound && arr[1][2]<bound && arr[2][2]<bound){
    long l = Math.max(arr[0][1],Math.max(arr[1][1],arr[2][1]));
    long r = Math.min(arr[0][2],Math.min(arr[1][2],arr[2][2]));
    if(l>r){
        if(arr[0][2]<=arr[1][2] && arr[0][2]<=arr[2][2]){
            arr[0][1]+=arr[0][0];
            arr[0][2]+=arr[0][0];
        }
        else if(arr[1][2]<=arr[0][2] && arr[1][2]<=arr[2][2]){
            arr[1][1]+=arr[1][0];
            arr[1][2]+=arr[1][0];
        }
        else{
            arr[2][1]+=arr[2][0];
            arr[2][2]+=arr[2][0];
        }
    }
    else{
        System.out.println(l);
        return;
    }
}

 

만약 최소 공배수까지 진행했을 때 끝내지 못했다면 -1을 출력합니다. 

 

전체 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.*;
import java.util.*;


public class Main {

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

        Long[][] arr = new Long[3][3];

        for (int i = 0; i < 3; i++) {
            String[] s = br.readLine().split(" ");
            arr[i][0] = Long.parseLong(s[0]);
            arr[i][1] = Long.parseLong(s[1]);
            arr[i][2] = Long.parseLong(s[2]);
        }

        Arrays.sort(arr, (a, b) -> {
            return (int) (a[0] - b[0]);
        });

        long bound = arr[0][0]*arr[1][0]*arr[2][0]+1;

        while(arr[0][2]<bound && arr[1][2]<bound && arr[2][2]<bound){
            long l = Math.max(arr[0][1],Math.max(arr[1][1],arr[2][1]));
            long r = Math.min(arr[0][2],Math.min(arr[1][2],arr[2][2]));
            if(l>r){
                if(arr[0][2]<=arr[1][2] && arr[0][2]<=arr[2][2]){
                    arr[0][1]+=arr[0][0];
                    arr[0][2]+=arr[0][0];
                }
                else if(arr[1][2]<=arr[0][2] && arr[1][2]<=arr[2][2]){
                    arr[1][1]+=arr[1][0];
                    arr[1][2]+=arr[1][0];
                }
                else{
                    arr[2][1]+=arr[2][0];
                    arr[2][2]+=arr[2][0];
                }
            }
            else{
                System.out.println(l);
                return;
            }
        }

        System.out.println(-1);
    }
}