BOJ 2097 (S5) 조약돌
문제 요약
2차원 좌표평면에서의 정수 순서쌍 n개를 모두 포함하는 최소 직사각형의 둘레를 구해보자.
(단, n개의 좌표는 모두 다르다.)
풀이 방향
조약돌을 바닥에 던지면 보통은 탑이 쌓여 지지는 않기 때문에(그리고 쌓이면 2차원을 벗어난다.) 모든 좌표가 다르다고 설정하고 문제 풀이를 진행했다.
직사각형의 둘레가 최소가 되려면 면적도 최소가 되어야 한다.
즉, 점이 각각 가까이에 분포해야한다.
이때 두 직사각형2*4, 3*3은 면적은 다르지만 둘레는 동일한데, 문제를 쉽게 풀 수 있는 식으로 정리해보도록 하자.
제출 답안
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
if(n<3)
cout << 4;
for(int i=2; i<n; i++) {
if(n<=i*i) {
cout << (i-1)*4;
break;
} else if(n<=i*(i+1)) {
cout << (i-1)*4+2; //(i-1)*2 + i*2
break;
}
}
return 0;
}답안 해설
처음에 문제를 풀기 위해서 직사각형을 많이 그려보면서 몇 번의 시행착오 끝에 결론을 찾았다.
정사각형 형태에서 가장 많은 조약돌 개수를 가질 수 있다는 점이다.
그런데 여기에도 조금 까다로운 점이 있다.
예를 들어 5의 경우에는 4 < 5 <= 9이므로 위를 적용하면 면적이 2*2=4인 정사각형에는 당연히 포함되지만, 면적이 2*1=2인 직사각형에도 충분히 포함되어서 정답은 최솟값인 6이 된다.
따라서 나는 정사각형을 먼저 고려하되, 각 정사각형 사이의 직사각형을 추가로 배치했다.
정사각형의 둘레는 4의 배수이고, 직사각형의 둘레는 짝수이므로 각 정사각형 사이의 직사각형이 오직 하나 존재하게 된다.
마지막으로, 조약돌을 포함하는 직사각형은 무조건 존재해야 한다.
n=1,2의 경우에는 한 직선 위에 존재할 수 있어서 1*1 면적의 직사각형 둘레 1*4=4로 계산해주었다.
이 문제와 관련된 좋은 문제
BOJ 2163 (B1) 초콜릿 자르기
추가로 읽어보기 좋은 재미있는 글
