알고리즘/백준
[14223] 작은 정사각형1 - 브루트포스, 조합, 수학 (백준, Java)
son_i
2025. 12. 10. 19:38
728x90
▶️시도했던 과정
조합으로 N개 점 중 N - 2개를 뽑아 풀었으나 시간초과. 재귀할 때 순열처럼 계속 0부터 돌고있었다.
제외할 2개의 점을 뽑는게 키포인트였고 넓이 구하는 로직에도 문제가 있었다.
1차시도 - 시간초과
보자마자 N 개 중 N - 2개를 순서 없이, 중복 없이 뽑는 조합으로 풀면 될 것이라 생각했다.
조합 부분 & 넓이 구하는 부분 코드
private static void combination(int cnt) {
if (totalCnt == cnt) {
getWidth();
return;
}
for (int i = 0; i < N; i++) {
if (flagArr[i] == 0) {
flagArr[i] = 1;
cnt++;
combination(cnt);
cnt--;
flagArr[i] = 0;
}
}
}
private static void getWidth() {
long minX = Long.MAX_VALUE;
long minY = Long.MAX_VALUE;
long maxX = Long.MIN_VALUE;
long maxY = Long.MIN_VALUE;
for (int i = 0 ; i < N; i++) {
if (flagArr[i] == 1) {
Point cur = pointArr[i];
if (cur.x < minX) minX = cur.x;
if (cur.y < minY) minY = cur.y;
if (cur.x > maxX) maxX = cur.x;
if (cur.y > maxY) maxY = cur.y;
}
}
long x = Math.abs((minX - 1) - (maxX + 1));
long y = Math.abs((minY - 1) - (maxY + 1));
if (answer > x * y) answer = x * y;
}
totalCnt를 N - 2개로 설정해두고 cnt가 해당 수와 같아지면 그 N - 2 개의 점들의 각 x,y 최소 최대 값들을 뽑아 최소 넓이를 구한다.
→ 시간초과
N이 최대 50이니까 50개에서 48개를 뽑는 경우의 수는 1225가지가 나온다.
다만 이미 선택했거나 제외한 점에 대한 정보를 flagArr[i]로 체크하고 있음에도 활용하지 못 하고 매번 반복문에서 0부터 탐색한다.
이러면 순열처럼 N!의 시간 복잡도를 갖게 된다.
재귀호출 시 다음 인덱스부터 탐색하도록 제한해야 O(N^2) 내에서 효율적인 동작을 할 수 있다.
2차 시도 - startIdx로 재귀 시 처음부터 탐색하는 것을 막았지만 시간초과
따라서 이 코드로 조합 부분을 변경하였다.
private static void combination(int cnt, int start){
if(cnt == totalCnt){
getWidth();
return;
}
for(int i = start; i < N; i++){
if(flagArr[i] == 0){
flagArr[i] = 1;
combination(cnt+1, i+1);
flagArr[i] = 0;
}
}
}
다만 이것도 시간 초과가 나게 되는데 수학적으로는 NC2와 NCN-1가 같지만
이 로직같은 경우에 N 50이면 40번째부터 요소 1개를 뽑아도 48개가 당연히 안 되는데 끝까지 시도하게 된다. 이런 불필요한 시도로직에 시간이 많이 소요가 된다.
따라서 totalCnt (N-2)가 아닌 제외할 점 2개를 뽑는 로직으로 변경해준다.
▶️Solution Code1 - 조합로직
import java.io.*;
import java.util.*;
public class Main {
static int totalCnt;
static int N;
static Point[] pointArr;
static int[] flagArr;
static long answer = Long.MAX_VALUE;
static class Point {
long x;
long y;
public Point(long x, long y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
pointArr = new Point[N];
flagArr = new int[N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
pointArr[i] = new Point(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));
}
combination(0, 0);
System.out.println(answer);
}
private static void combination(int cnt, int startIdx) {
if (2 == cnt) {
getWidth();
return;
}
for (int i = startIdx; i < N; i++) {
if (flagArr[i] == 0) {
flagArr[i] = 1;
combination(cnt + 1, i + 1);
flagArr[i] = 0;
}
}
}
private static void getWidth() {
long minX = Long.MAX_VALUE;
long minY = Long.MAX_VALUE;
long maxX = Long.MIN_VALUE;
long maxY = Long.MIN_VALUE;
for (int i = 0; i < N; i++) {
if (flagArr[i] == 1) continue;
Point cur = pointArr[i];
if (cur.x < minX) minX = cur.x;
if (cur.y < minY) minY = cur.y;
if (cur.x > maxX) maxX = cur.x;
if (cur.y > maxY) maxY = cur.y;
}
long dx = maxX - minX + 2;
long dy = maxY - minY + 2;
long side = Math.max(dx, dy);
long curArea = side * side;
if (answer > curArea) answer = curArea;
}
}
근데 이것을 굳이 조합로직이 아니라 어차피 제외할 2개의 점을 뽑는 거라 이중 반복문으로도 가능하다.
▶️Solution Code2 - 이중 반복문 로직
import java.io.*;
import java.util.*;
public class Main {
static int N;
static Point[] pointArr;
static long answer = Long.MAX_VALUE;
static class Point {
long x;
long y;
public Point(long x, long y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
pointArr = new Point[N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
pointArr[i] = new Point(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));
}
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
getWidth(i, j);
}
}
System.out.println(answer);
}
private static void getWidth(int exclude1, int exclude2) {
long minX = Long.MAX_VALUE;
long minY = Long.MAX_VALUE;
long maxX = Long.MIN_VALUE;
long maxY = Long.MIN_VALUE;
for (int i = 0; i < N; i++) {
if (i == exclude1 || i == exclude2) continue;
Point cur = pointArr[i];
if (cur.x < minX) minX = cur.x;
if (cur.y < minY) minY = cur.y;
if (cur.x > maxX) maxX = cur.x;
if (cur.y > maxY) maxY = cur.y;
}
long dx = maxX - minX + 2;
long dy = maxY - minY + 2;
long side = Math.max(dx, dy);
long curArea = side * side;
if (answer > curArea) answer = curArea;
}
}
여기에 넓이 구하는 getWidth()로직도 처음엔 다음과 같이 작성해서 틀렸었다.
private static void getWidth(int exclude1, int exclude2) {
long minX = Long.MAX_VALUE;
long minY = Long.MAX_VALUE;
long maxX = Long.MIN_VALUE;
long maxY = Long.MIN_VALUE;
for (int i = 0; i < N; i++) {
if (i == exclude1 || i == exclude2) continue;
Point cur = pointArr[i];
if (cur.x < minX) minX = cur.x;
if (cur.y < minY) minY = cur.y;
if (cur.x > maxX) maxX = cur.x;
if (cur.y > maxY) maxY = cur.y;
}
long x = Math.abs((minX - 1) - (maxX + 1));
long y = Math.abs((minY - 1) - (maxY + 1));
if (answer > x * y) answer = x * y;
}
x, y 각각 최대, 최소 값들의 절댓값을 곱해서 계산했는데 이러면 직사각형이 된다.
x와 y 값 중 더 큰 값을 택해서 (그래야 모든 점이 덮어지니까) 그 값으로 제곱을 해 정사각형의 넓이를 구해야한다.
따라서 올바른 getWidth()는 다음과 같다.
private static void getWidth() {
long minX = Long.MAX_VALUE;
long minY = Long.MAX_VALUE;
long maxX = Long.MIN_VALUE;
long maxY = Long.MIN_VALUE;
for (int i = 0; i < N; i++) {
if (flagArr[i] == 1) continue;
Point cur = pointArr[i];
if (cur.x < minX) minX = cur.x;
if (cur.y < minY) minY = cur.y;
if (cur.x > maxX) maxX = cur.x;
if (cur.y > maxY) maxY = cur.y;
}
long dx = maxX - minX + 2;
long dy = maxY - minY + 2;
long side = Math.max(dx, dy);
long curArea = side * side;
if (answer > curArea) answer = curArea;
}
고민의 흔적들..
728x90