[랜덤 마라톤] 최소공배수 찾기(11688)

1. 문제 풀이 아이디어

• 반복문을 순회하며 a, b, i의 최소공배수가 L인 경우를 찾아 문제를 해결한다.

• c가 될 수 있는 조건을 계산하여 반복 횟수를 줄여 시간 초과를 방지한다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        long a = Long.parseLong(stringTokenizer.nextToken());
        long b = Long.parseLong(stringTokenizer.nextToken());
        long l = Long.parseLong(stringTokenizer.nextToken());
        long ab = a * b / gcd(a, b);
        long result = -1;
        if (l == ab) {
            result = 1;
        } else if (l % ab == 0) {
            long inc = l / ab;
            for (long i = inc; i <= l; i += inc) {
                if (l % i != 0) continue;
                long gcd = gcd(ab, i);
                if (ab * i / gcd == l) {
                    result = i;
                    break;
                }
            }
        }
        System.out.println(result);
        bufferedReader.close();
    }

    private static long gcd(long a, long b) {
        if (a % b == 0) return b;
        return gcd(b, a % b);
    }
}

3. 정리

• a와 b의 최소공배수를 구해 ab에 저장한다.

• c가 불가능한 경우를 대비해 결과값을 -1로 초기화한다.

• l과 ab가 같다면 c는 1이 된다.

• l이 ab로 나누어떨어지는 경우에만 c를 구할 수 있으므로, l % ab == 0 조건을 확인한다.

• c는 l과 ab의 몫의 배수이므로, 이를 inc에 저장하고 inc의 배수로 l 이하까지 반복한다.

• l이 i로 나누어떨어지지 않으면 건너뛴다.

• ab와 i의 최소공배수가 l과 같다면 결과를 저장하고 반복문을 종료하여 문제를 해결한다.