백준 25342번
https://www.acmicpc.net/problem/25342

문제

---

생각하기

---

• 유클리드 호제법을 사용해서 최소공배수를 구해야 한다.

• 3개의 값을 임의로 선택해서 최소공배수 중에서 최대값을 찾는다.

• 32비트의 정수 범위를 넘어설 수 있다고 했기 때문에 Long(64비트)로 결과값을 받아야 한다.

동작

        val tmp1: Long = LCM(LCM(N - 3, N - 2), N - 1)
        val tmp2: Long = LCM(LCM(N - 2, N - 1), N)

        if (N % 2 == 0L) {
            println(
                Math.max(Math.max(tmp1, tmp2), LCM(LCM(N - 3, N - 1), N))
            )
        } else {
            println(
                Math.max(Math.max(tmp1, tmp2), LCM(LCM(N - 3, N - 2), N))
            )
        }

1부터N으로 들어오는 값 까지의 숫자 중 3개의 값을 임의로 선택해서 최소공배수 중 최대값을 찾으면 되는데,

당연히 큰 수인 뒤에서 부터 탐색을 해야 최소공배수 중에서 최대값을 찾을 수 있다는 생각을 했다.

처음에 1씩 차이가 나는 값은 당연히 조건에 포함을 해야한다고 생각했고,

N에 여러가지 값을 대입해봤을 때, 1씩 차이가 나도 N이 포함되지 않는 값이 최대가 나올 수 있다는 것을 알게되었다.

예를 들면 N이 29, 30일 경우 둘의 결과 값은 같게 나오는데

N = 29
LCM(26, 27, 28) : 9828

LCM(26, 27, 29) : 20358

LCM(26, 28, 29) : 10556

LCM(27, 28, 29) : 21924

N = 30
LCM(28, 29, 30) : 12180

LCM(27, 29, 30) : 7830

LCM(27, 28, 29) : 21924

LCM(27, 28, 30) : 3780

30에서도 LCM(27, 28, 29)의 값이 가장 높게 나오므로 결국 29의 결과값이 30의 결과값과 같음을 알 수 있었다.

이렇게 되면 단순히 최대값 N에서 1의 차이값은 정답이 될 수 없음을 의미했다

위와 같이 2개의 조건을 생각 할 수 있었고, 또한 N의 값을 기준으로 홀수가 2개가 포함되는 경우가 훨씬 큰 값이 나옴을 유추할 수 있었다.

예를 들어 N이 15와 16일 경우

N = 15

LCM(12, 13, 15) : 780

LCM(12, 14, 15) : 420

N = 16

LCM(13, 14, 16) : 1456

LCM(13, 15, 16) : 3120

15의 정답은 2730 이기 때문에 정답은 아니지만, 대충 유추를 해보자면 홀수가 2개가 들어갔을 때가 큰 값이 나옴을 알 수 있었다.

따라서 N이 짝수 일 때의 조건과 홀수 일 때의 조건으로 분리해서 3개의 숫자 중에 홀수가 2개가 들어갈 수 있도록 하는 조건을 추가해서 총 3번의 LCM메소드를 실행하여 정답을 구할 수 있었다.

코드

---

Kotlin

import java.io.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var T = br.readLine().toInt()
    while (T-- > 0) {
        val N = br.readLine().toLong()

        val tmp1: Long = LCM(LCM(N - 3, N - 2), N - 1)
        val tmp2: Long = LCM(LCM(N - 2, N - 1), N)

        if (N % 2 == 0L) {
            println(
                Math.max(Math.max(tmp1, tmp2), LCM(LCM(N - 3, N - 1), N))
            )
        } else {
            println(
                Math.max(Math.max(tmp1, tmp2), LCM(LCM(N - 3, N - 2), N))
            )
        }
    }
} // End of main

private fun GCD(a: Long, b: Long): Long {
    if (a % b == 0L) return b
    return GCD(b, a % b)
} // End of GCD

private fun LCM(a: Long, b: Long): Long {
    return (a * b) / GCD(a, b)
} // End of LCM