[자바] 백준 2859 - 별 관찰 (java)

 문제 : boj2859

---

 

필요 알고리즘 개념

• 수학, 정수론, 브루트포스
  
  • 수식을 정리해 브루트포스로 모든 경우를 살펴보면서 나누어떨어지는 경우를 찾아야한다.
• 비둘기집의 원리
  • 좀 더 명확하게 횟수를 지정하고 싶거나, 몇 번 해야 Never인지 따로 판단하지 않으려면 이게 필요하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 시간과 분으로 된 문자열은 처리하기가 상당히 까다롭다. 그러니 우선 정수로 변환하기 위해 입력값을 전부 '분'으로 치환한 후 사용하자.

 

  예를들어 예제 입력 1의 경우

02:20
13:00
05:50
01:00

각각 140, 780, 350, 60분이 된다.

 

  입력값 순서대로 $s1$, $s2$, $f1$, $f2$ 라고 하자.

이 때 말로 설명된걸 수식으로 바꿔보자. 첫 번째 별이 $t$시간, 두 번째 별이 $y$시간이 지났다고 해보자. 예를들어 위의 경우 첫 시작에서 첫 번째 별은 $140+350*0$분, 1시간이 지난후 $140+350*1$분, $t$시간이 지난후 $140+350*t$분 위치에 있다.

 

  이 문제는 결국 $s1+f1*t = s2+f2*y$인 경우가 있냐고 묻는 문제이고, 식을 좀 정리해보면 

$\frac{s1+f1*t-s2}{f2} = y$ 에서 $y$가 양의 정수로 가능하냐는거다.

 

 그럼 결국 우리가 구하고자 하는건 $t$ 시간이 지났을 때,

$s1+f1*t-s2$ 가 $f2$로 나누어떨어지는 경우가 있냐는 문제라고 볼 수 있다. ($t=[0 ,\infty ]$)

나누어떨어진다면 양의 정수 $y$가 가능하다.

 

  그럼 그냥 $t$를 0부터 무한대로 증가시키면서 $f2$로 나누어떨어지는지 확인만하면 끝난다! 해당 경우를 찾았다면, 분으로 치환해둔걸 다시 분과 시간으로 바꾸고 요일을 구해주면 된다. 어떻게 분, 시간, 요일을 구하는지는 코드를 참고해보자.

 for (int i = 0; i < LIMIT; i++) {
    int cur = s1 + f1*i;
    if (cur-s2<0 || (cur-s2)%f2 != 0) continue;
    // 위 if문에 안걸렸으면 답에서 찾고자 하는 경우임!
}

  

---

 

  이 문제에서 어려운 점은 '두 별이 동시에 반짝이지 않는다면 "Never"를 출력한다.' 라는 조건이다. 정말 $t$를 무한대로 증가시킨다면 시간 복잡도도 무한대로 가버린다. 따라서 특정 횟수까지만 시도해봐야할텐데, 그 횟수를 찾기가 어려웠다. 다만 이 문제는 상당히 널널한 문제라 대충 한 50만번으로 LIMIT을 잡고 수행해도 통과되긴한다 ㅋㅋ 그래서 실버3이다. 시간이 널널하지 않았다면 골드는 충분히 가능했을 것 같다.

 

  내가 판단한 제한 횟수는 1439번이다.

$s1$, $s2$, $f1$, $f2$의 최대치는 각각 1439분이다.

그렇다면 위에서 본 $s1+f1*t-s2$ 에서 s1-s2는 고정값이니 제외하고 생각해보면 결국 $f1$, $f1+f1$, $f1+f1+f1$... 처럼 증가하는 값이 $f2$로 나누어떨어지냐는 건데, 나머지 연산의 성질에 따라 당연하게도 나눈 나머지는 $f2$ 이하이다. 또한 나머지 연산의 다음과 같은 규칙에 따라

 

  매번 $f2$로 나누어놓아도 최종 답을 구하는데 문제가 없다.

그렇다면, 1439 이하인 나머지 연산의 결과가 동일한 값이 뜨는 경우는 사이클이 생긴 경우라는 얘기가 된다. 즉, 기존에 나온 결과가 다시 나온다면 답을 찾지 못하고, 무한히 진행되게 되는 경우인 것이다. 예를들어 매번 $f2$로 나눈 나머지가 1->3->5->1 처럼 다시 나왔다고 해보자, 그럼 그 이후로는 매번 1->3->5가 무한 반복될 것임을 알 수 있고, 답을 찾지 못하고 무한히 진행될 것이다.

 

  따라서 비둘기집의 원리에 따라 사이클이 생기지 않고 1439이하에서 동일한 값이 뜨지 않는 경우의 수는 1439회이므로, 1439회로 설정했다. 그게 코드1 이다.

 

  TMI. 다만 여기서 $s1-s2$가 최소 -1439가 가능하고, $s1+f1*t-s2$가 음수인 경우는 나누어떨어지는지 체크할 필요가 없다. 그러니 이론상(?) 음수부분을 탈출할때까지 최대 1440회정도 필요하고, 그 뒤에 다시 나누어떨어지는지 찾으려면 2880회 정도로 설정하는게 맞을 것 같긴한데, 이 경우 음수를 탈출하는데 가장 느린 테스트케이스를 한번 생각해보면 다음과 같은 경우다.

00:00
23:59
00:01
23:59

---

00:00
23:59
00:02
23:59

  첫 번째 경우는 -1439에서 +1씩 음수 부분을 탈출하는데, 어쨌든 +1씩이라 음수만 탈출하면 바로 답이 나와서 1439회만에 끝난다. 두 번째 경우는 -1439에서 +2씩 음수 부분을 탈출하는데, 어쨌든 +2씩 증가하다보니 이론상 2880회의 절반이면 된다. 결론적으로 얘도 1439회만에 답이 찾아진다. 그래서 더 큰 수로 해도 비슷할 것 같긴한데, 특정 수에서 1439회보다는 더 많은 횟수가 필요할수도 있을 것 같다. 시간 복잡도 상으로 1440으로 하던지 2880으로 하던지 큰 차이는 없으므로 원하는걸 선택하면 될 것 같다. 사실 애초에 문제 채점 테스트케이스가 약해서 700회로 해도 통과된다. (1439회짜리 테스트케이스 추가 요청 넣어놓긴했다 ㅋㅋ). 그리고 랜덤 TC생성해서 추가로 검증해봐도 되지만 굳이 안한 이유는, 코드2에선 횟수를 지정하지 않고 풀기 때문이다. 

 

  횟수 지정하는건 상당히 하드코딩스럽고, 위의 증명이 확실한지도 모르겠다. 그럼 확실하게 위에서 설명한 방식을 적용해 비둘기집의 원리로 나눈 나머지 결과에 사이클이 생기면 Never를 출력해도 된다. 그게 코드2 이다.

 

---

 

코드1 (횟수 지정) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final int LIMIT = 1440;
    private static final String[] DAYS = {"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int s1 = getMin(br.readLine());
        int s2 = getMin(br.readLine());
        int f1 = getMin(br.readLine());
        int f2 = getMin(br.readLine());

        for (int i = 0; i < LIMIT; i++) {
            int cur = s1 + f1*i;
            if (cur-s2<0 || (cur-s2)%f2 != 0) continue;

            int min = cur%60;
            cur/=60;
            int hour = cur%24;
            cur/=24;

            System.out.println(DAYS[cur%7]);
            System.out.println(lpad(hour) + ":" + lpad(min));
            return;
        }
        System.out.println("Never");
    }

    private String lpad(int num) {
        if (num < 10)
            return "0"+num;
        return String.valueOf(num);
    }

    private int getMin(String hhmm) {
        String[] split = hhmm.split(":");
        return Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);
    }
}

 

 

코드2 (사이클 판정) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final String[] DAYS = {"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int s1 = getMin(br.readLine());
        int s2 = getMin(br.readLine());
        int f1 = getMin(br.readLine());
        int f2 = getMin(br.readLine());
        HashSet<Integer> hs = new HashSet<>();

        int i = 0;
        while (true) {
            int cur = s1 + f1*i++;
            if (cur-s2<0) continue;

            int tmp = (cur-s2)%f2;
            if (hs.contains(tmp)) break;
            hs.add(tmp);

            if (tmp != 0) continue;

            int min = cur%60;
            cur/=60;
            int hour = cur%24;
            cur/=24;

            System.out.println(DAYS[cur%7]);
            System.out.println(lpad(hour) + ":" + lpad(min));
            return;
        }
        System.out.println("Never");
    }

    private String lpad(int num) {
        if (num < 10)
            return "0"+num;
        return String.valueOf(num);
    }

    private int getMin(String hhmm) {
        String[] split = hhmm.split(":");
        return Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);
    }
}