[백준] 2097번 - 조약돌 (C++)

 

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

 

 

 

출력

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

 

 

 

풀이과정

예제 해석

예제를 해석해보자면 위와 같다.

돌을 최대한 배치를 잘해서 둘레를 가장 작게 만들면 되는 문제였었는데

직사각형의 둘레를 구하는 공식이 ( a * 2 ) + ( b * 2 ) 이다보니 a + b의 값을 가장 작게 만들면 되는 문제였다.

a + b를 가장 작게 만들려면 예제와 같이 1 + 2 이거나 3 + 3이거나 인 형식이다보니 규칙성을 비교해보면 a 와 b의 값의 차이가 가장 작을 수록 둘레의 최소길이가 된다는 것을 알 수 있기때문에 a ± 1 >= b 라는 형식의 식이 성립해야한다는 것을 확인해볼 수 있었다.

그래서 n이라는 값에 제곱수를 구하게 되면 a ± 1 >= b 라는 식에 가장 성립이 되는 값이 나오게 되어 풀이를 진행하게 되었었다.

 

문제에서는 "직사각형의 가로와 세로 길이는 반드시 1 이상이어야 한다."  라는 조건식이 있다보니

n 이 1이나 2인 경우에도 가로 세로의 길이를 1로 계산을 해줘야한다. ( answer = 4 )

 

 

 

code

#include <iostream>
#include <math.h>

int		main(void)
{
	int n, root;
	std::cin >> n;
	if (n == 1 || n == 2)
		std::cout << 4;
	else {
		root = std::round(std::sqrt(n));
		if (root * root >= n)
			std::cout << (root - 1) * 4;
		else
			std::cout << ((root - 1) * 2) + ((root) * 2);
	}

	return (0);
}

 

후기

머리로는 이해가되지만 어떻게 점화식을 세워야할지 은근 고민을 많이했던 문제였던 거 같다.

수학적인 개념을 조금 더 공부를 많이해야할 거 같다.