[자바] 백준 25487 - 단순한 문제 (Large) (java)

 문제 : boj25487

---

 

필요 알고리즘 개념

• 수학 (정수론)
  
  • 나머지 연산에 대한 수학적 지식이 있어야 풀 수 있다.

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

 

---

 

풀이

  당연히 그냥 구하려 하면 O(Tabc)라는 엄청난 수치가 나온다. (대략 6x10^15)

mod 연산의 성질을 이용해 풀어야 한다. 의식의 흐름은 다음과 같다.

 

0. (x mod y) = (y mod z) = (z mod x) 에 대해

 

1. (x mod y) <= x (당연히 x를 y로 나눈 나머지인데 x보다 클 순 없다), (y mod z) <= y, (z mod x) <= z 이다.

 

2. 이 때, (x mod y) == x 려면 x<y 여야 한다 (예를들어 3 mod 5 = 3이다.) 마찬가지로 (y mod z) == y려면 y < z, (z mod x) == z려면 z < x 여야 한다. 근데 식'0'이 만족해야 하므로 y>x>z>y 가 되어 모순이 된다. 따라서 이 경우는 빼버린다.

 

3. 그럼 식'1'에서 (x mod y) < x, (y mod z) < y, (z mod x) < z 만 남긴다.

 

4. (x mod y) < x 가 되려면 x>=y 여야 한다('2'에서 봤듯이 x<y라면 결과는 x와 같아진다. x보다 작아지려면 x>=y여야 한다). 마찬가지로 (y mod z ) < y 면 y>=z, (z mod x) < z면 z>=x 이다. 따라서 식'0'을 만족하려면 x>=y>=z>=x 이므로, x == y == z 여야 한다.

 

5. x==y==z 인 경우의 수는 결국min(a,b,c)와 동일하다.

 

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            sb.append(Math.min(a, Math.min(b, c))).append('\n');
        }
        System.out.print(sb);
    }

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