[수학] 백준 25487번 단순한 문제 (Large) - JAVA

 

오늘은 해당 문제로 시간 복잡도를 줄일 수 있는 설계에 대해 생각해볼 수 있었다.

 

---

1. 출처

---

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

25487번: 단순한 문제 (Large)

 

• (x%y) = (y%z) = (z%x) 에 부합하는 (x, y, z) 쌍이 몇 개인지 알아내는 문제
• 1<=x<=a, 1<=y<=b, 1<=z<=c 범위 안에서 쌍을 구하면 됨 문제에서 a,b,c는 주어짐

 

---

2. 설계

---

 

(x%y) = (y%z) = (z%x)를 만족하는 쌍을 찾기 위해선 가장 먼저 생각나는 방법은 3중 for이다. 근데 O(N^3)의 방법론은 2.4초 안에 끝내지 못한다. 왜냐하면 a,b,c는 최대 10만까지 나올 수 있기 때문에 3중 for은 10만x10만x10만 = 1000만의 연산이 기다리고 있다. 또한 테스트 케이스 최대 60만 개가 기다리고 있기 때문에 최종적으로 1000만 x 60만 = 60000만 = 6억의 연산이 기다리고 있는 것이다...

즉, 3중 for은 6초가 필요한 연산이다.

 

그래서 자연스럽게 수식을 정리하려고 노력했다.

1) (a%b)는 a를 b로 나눴을 때 나머지이다. 때문에 이 나머지는 원래 수 a보다 클 순 없다.

그래서 아래와 같은 식이 성립된다.

(a%b) <= a

(b%c) <= b

(c%a) <= c

 

2) 근데 (a%b)==a가 되려면 b는 a보다 커야한다. 예를 들어 2%5 = 2인 것처럼 말이다.

그래서 아래와 같은 식이 성립된다.

if (a%b) == a, a<b

if(b%c) == b, b<c

if(c%a) == c, c<a

 

이걸 정리해보면 a<b<c<a 라는 모순이 발생한다는 것을 알 수 있다. 따라서 2번 가정은 있을 수 없는 일이다.

즉, 1번 가정에선 같다는 전제를 제외하고, 아래 경우만 생각한다.

(a%b) < a

(b%c) < b

(c%a) < c

 

3) 그렇다면 (a%b)<a가 되기 위해선 a>=b여야 한다. 예를 들어 2%2 == 0이고, 6%4 == 2이다.

그래서 아래와 같은 식이 성립된다.

if (a%b) < a, a>=b

if(b%c) < b, b>=c

if(c%a) < c, c>=a

 

이걸 정리해보면 a>=b>=c>=a라는 모순이 또 발생한다는 것을 알 수 있다.

해당 식을 성립하기 위해선 a=b=c가 최선임을 확인할 수 있다.

 

최종적으로 (x,y,z)는 모두 같은 수이다. 때문에 minimum 값이 정답이 될 수 밖에 없다.

 

 

---

3. 전체 코드

---

 

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

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

        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int T=1;T<=t;T++){
            String abc = br.readLine();
            StringTokenizer st = new StringTokenizer(abc," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            int min = Math.min(a,(Math.min(b,c)));

            sb.append(min).append("\n");
            
        }//for T

        System.out.println(sb);
        br.close();
    }
}

 

 

 

참고 블로그

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