Codeforces Round #530 (Div. 2) B. Squares and Segments

문제링크 : https://codeforces.com/contest/1099/problem/B

원하는 개수의 사각형을 만들기 위해 자를 재고 그려야하는 선의 개수의 최소값을 찾는 문제이다.

우선 이해하기 쉽게 문제를 설명해보면, 위 그림에서 빨강색 선은 자를 이용해서 그려야 하는 부분, 검정색은 자 없이도 그릴 수 있는 부분이다.

왜 검정색은 자 없이 그릴 수 있는 부분인가? 이미 같은 x 와 (x+1) 혹은 같은 y와 (y+1)을 이은 선이 존재하기 때문이다.

즉, a'은 a로 인해 자 없이 그릴 수 있고, b'은 b로 인해 자 없이 그릴 수 있게 된다.

마찬가지로 사각형 2개를 만들기 위해서는 아래 그림과 같이 구성되어야 한다.

사각형 2개를 만들기 위해서는 3개의 빨강 선이 필요하게 된다.

이제, 만들고 싶은 사각형의 개수가 주어진다. 그리고 필요한 빨강색 선의 최소 개수를 출력해야 한다.

먼저, 원하는 사각형의 개수를 n이라고 한다.

이 때, n보다 작거나 같은 제곱수중 최대값을 구해야한다.

왜냐하면, 빨강색이 16개가 있다고 생각해보자. 이 때, 이 빨강색 선들을 구성해서 가장 많은 사각형을 만들기 위해서는 가로 8개 세로 8개가 필요하다.

(수학적 증명은 생략! 간단하게 설명하면 a+b = 8일 때, 양변을 제곱해서 ab가 최대가 되려면 a^2+b^2이 최소가 돼야한다.)

따라서 먼저 pow ( n, 0.5 )를 하여 n보다 작거나 같은 제곱수의 제곱근을 구한다. 이 제곱근을 minimum이라고 한다.

다음으로 우리가 처리해야할 부분은 n에서 제곱수를 뺀 남은 부분이다.

우리가 추가할 수 있는 선은 최대 2개이다. ( 가로 1개, 세로 1개를 더할경우 minimum+1의 제곱수만큼 만들 수 있으므로)

즉, n에서 minimum^2을 뺀 값이 minimum보다 클 경우 (minimum개의 사각형보다 더 많이 필요한 경우)에는 2개를 더해주고 minimum보다 작을 경우에는 1개를 더해주면 된다.

단, 추가로 필요한 사각형의 개수가 0일 때는 반드시 예외처리 !

---

- 소스코드 -

#include<iostream>
#include<math.h>
 
using namespace std;
 
int main(void) {
    int n;
    cin >> n;
    int minimum = pow(n, 0.5);
    int result = minimum * 2;
    n -= minimum * minimum;
    while (n > 0) {
        result++;
        n -= minimum;
        minimum++;
    }
    
 
    cout << result << endl;
}

+ 소스코드에서 사용한 방법은 선을 1개 추가해보고 부족하면 1개 더 추가하는 방법이다.

---