[BOJ] 2097 - 조약돌

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

BOJ - 조약돌

문제 유형: 수학, 기하학, 사칙연산

문제 난이도: Silver V

시간 제한: 1초

메모리 제한: 128MB

 

문제

당신은 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)이 주어진다.

 

출력

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

 

풀이

산술평균 - 기하평균의 관계에 의해, 균일한 너비와 높이를 가지면, 같은 둘레에서 최대 넓이가 나온다, x, y를 1씩 증가하면서 n개이상 커버가능한지 확인하고 가능하면 출력하고 종료한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(int argc, char *argv[]) {
    ll n;
    cin >> n;

    ll x = 1, y = 1;
    while (true) {
        if ((x + 1) * (y + 1) >= n) {
            cout << 2 * (x + y) << "\n";
            break;
        }
        x++;
        if ((x + 1) * (y + 1) >= n) {
            cout << 2 * (x + y) << "\n";
            break;
        }
        y++;
    }

    return 0;
}