[백준] 2097

조약돌

문제

당신은 N개의 조약돌을 가지고 있다. 이 조약돌을 좌표평면의 격자점 위에 아무렇게나 떨어뜨렸다. 격자점이란, x좌표와 y좌표 모두가 정수인 지점을 말한다. 이를테면 (1, 1)이나 (0, -9)는 격자점이며, (-2, 3.5)이나 (π, 7.14)는 격자점이 아니다.

모든 조약돌을 포함하는 가장 작은 직사각형을 생각할 수 있다. 예를 들어 세 개의 조약돌을 (2,4), (4, 8), (5,5)에 떨어뜨렸다면, 이 세 조약돌을 모두 포함하는 가장 작은 직사각형은 가로 3, 세로 4인 직사각형이다. 이 경우 직사각형의 둘레는 14가 된다. 직사각형의 가로와 세로 길이는 반드시 1 이상이어야 한다.

조약돌의 개수 N이 주어졌을 때, 조약돌을 좌표평면의 격자점에 적절히 떨어뜨려서 모든 조약돌을 포함하는 직사각형의 둘레를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 조약돌의 개수 N(1 ≤ n ≤ 500,000,000)이 주어진다.

출력

첫째 줄에 최소 둘레를 출력한다.

풀이

#include <iostream>
#include <cmath>

int main(void) {
    int n;

    std::cin >> n;
    if (n == 1 || n == 2) std::cout << 4;
    else {
        int nearest = std::floor(std::sqrt(n));
        if (nearest * nearest == n) {
            std::cout << 4 * (nearest - 1);
        } else {
            if (nearest * nearest + nearest >= n)
                std::cout << 2 * (nearest + nearest - 1);
            else
                std::cout << 4 * (nearest);
        }
    }
}

반성회

1 => 2(1+1) = 4

2 => 2(1+1) = 4
3 => 2(1+1) = 4
==============================
4 => 2(0+2) = 4

5 => 2(1+2) = 6
6 => 2(1+2) = 6

7 => 2(2+2) = 8
8 => 2(2+2) = 8
==============================
9 => 2(1+3) = 8

10 => 2(2+3) = 10
11 => 2(2+3) = 10
12 => 2(2+3) = 10

13 => 2(3+3) = 12
14 => 2(3+3) = 12
15 => 2(3+3) = 12
==============================
16 => 2(2+4) = 12

17 => 2(3+4) = 14

17개 정도 일일이 계산해서 규칙을 찾았다

1. n이 1이거나 2인 경우
   • 가장 작은 직사각형의 둘레인 4
2. n이 제곱수인 경우
   • 둘레는 2 * (제곱근 + 제곱근 - 2)
3. n이 제곱수가 아닌 경우
   • n보다 작으면서 가장 가까운 제곱수의 제곱근을 nearest라고 하자
   • “가장 가까운 제곱수에 nearest를 더한 것”보다 n이 작을 경우, 둘레는 2 * (nearest + nearest)
   • “가장 가까운 제곱수에 nearest를 더한 것”보다 n이 크거나 같을 경우, 둘레는 2 * (nearest + nearest - 1)