[Kotlin] 백준 30704 : 정사각형 연결하기

문제 링크 : https://www.acmicpc.net/problem/30704

---

문제 해설

한 변의 길이가 1인 정사각형을 겹치지 않게 나란히 붙여서 둘레가 최소가 되는 다각형을 만들어야 합니다.

 

격자 형태의 공간에서 한 변의 길이가 1인 정사각형을 배치해서 도형을 만든다는 점에서 이 문제는 넓이가 \(N\)인 다각형 중에서 둘레가 가장 작은 다각형의 둘레를 구하는 것과 같다는 것을 알 수 있습니다.

 

우선 둘레를 구하기 전에 다각형이 정사각형 또는 직사각형이 아닌 경우에 대해 한번 보겠습니다.

\(N\)이 5인 경우에는 위와 같이 정사각형들을 배치할 수 있습니다.

 

이 경우에 대해 둘레를 구할 때 살짝 비틀어 보면 아래와 같이 둘레가 구해지는 것을 볼 수 있습니다.

직사각형에서 움푹 들어간 부분의 변을 바깥으로 이동하면 위와 같은 형태인 도형의 둘레는 꽉찬 직사각형의 둘레와 같다는 것을 알 수 있습니다.

 

직사각형의 둘레는 \(2\times(가로+세로)\)이므로 가로와 세로의 합계가 최소가 되어야 합니다.

 

다시 문제로 돌아와서 둘레의 최소 길이를 구해야하니 넓이가 \(N\)인 정사각형의 둘레를 구하는 문제로 바꿔볼 수 있습니다.

 

이 경우에는 각 변의 길이가 \(\sqrt{N}\)이 됩니다.

 

하지만 문제에서는 한 변의 길이가 1인 정사각형으로 구성되는 다각형이라는 언급이 있기 때문에 각 변의 길이는 정수라는 사실을 알 수 있습니다.

 

다시 말해 \(\sqrt{N}\)이 정수가 아니라면 \(\lfloor\sqrt{N}\rfloor\)이 한 변의 길이가 됩니다.

 

나머지 한 변의 길이는 자연스럽게 \(\frac{N}{\lfloor\sqrt{N}\rfloor}\)가 됩니다. 하지만 이 경우도 결과값이 실수가 나올 수 있기 때문에 \(\lceil\frac{N}{\lfloor\sqrt{N}\rfloor}\rceil\)와 같이 정수로 만들어줘야 합니다.

 

이 경우에 대한 예시로는 \(N=5\)인 경우를 들 수 있습니다.

 

\(N=10\)인 경우에는 \(\lfloor\sqrt{N}\rfloor=a=3\)가 되고 \(\frac{N}{\lfloor\sqrt{N}\rfloor}=b=3.33333\)이 됩니다. 하지만 여기서 \(b\)를 정수로 만들기 위해 반올림이나 내림을 하게 되면 \(a\times b=9\)가 되고 \(N\)보다 작은 정사각형이 만들어지게 됩니다.

 

대신 \(b\)를 올림 처리하면 \(a\times b=12\)가 되고 아래와 같은 모습으로 나타낼 수 있습니다.

위에서 본 것과 같이 이 도형에서 주황색으로 채워진 다각형의 둘레는 \(3\times4\)인 직사각형의 둘레와 같습니다.

 

즉, 문제에서는 각 테스트 케이스에 대해 \(2\times(\lfloor\sqrt{N}\rfloor+\lceil\frac{N}{\lfloor\sqrt{N}\rfloor}\rceil)\)를 구해서 출력해주면 됩니다.

Code

import kotlin.math.ceil
import kotlin.math.sqrt

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    repeat(readLine().toInt()) {
        val n = readLine().toDouble()
        val a = sqrt(n).toInt()
        val b = ceil(n / a).toInt()
        bw.write("${2 * (a + b)}")
        bw.newLine()
    }
    bw.close()
}