🌠 "두 스티커" - 16937번

🎃문제설명

크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다.

오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다.

두 스티커가 붙여진 넓이의 최댓값을 구해보자.

입력

첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.

출력

첫째 줄에 두 스티커가 붙여진 넓이의 최댓값을 출력한다. 두 스티커를 붙일 수 없는 경우에는 0을 출력한다.

🔒제한사항

• 1 ≤ H, W, N ≤ 100
• 1 ≤ Ri, Ci ≤ 100

💾입출력 예

입력	출력
2 2 2 1 2 2 1	4
10 9 4 2 3 1 1 5 10 9 11	56
10 10 3 6 6 7 7 20 5	0

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 기하학

🌟문제 이해 및 풀이계획

✏️이차원배열을 만들어서 스티커의 큰 변의 길이를 0번째, 작은 변의 길이를 1번째에 저장하고 내림차순 정렬하여 가장 넓이가 큰 순서대로 정렬하려고 했다. (근데 지금 생각해보니 변의 길이로 정렬하는 것이 꼭 넓이가 큰 순서가 아니라는 걸 깨달았다........😥

시행착오
✏️처음에는 H, W의 길이를 줄여가면서 계산했는데 그러면 모든 경우를 처음 H, W의 길이와 비교할 수 없게되니 새로운 변수 length를 설정하여 계산해 주었지만 H를 빼서 비교할지 W를 빼서 비교할지.. 문제 봉착.

✏️그래서 또다른 H, W를 max값과 min값을 구별해주어 새로운 변수를 만들어서 작은 변은 작은 값을 빼고 큰 변은 큰 값을 빼도록 했지만 반대의 경우도 있기 때문에 또 실패.

✏️그래서 머리가 뒤죽박죽 해져 강의를 보면서 하나씩 정리해 보았다..

✍🏻내 코드1 + 오답코드

package BOJ;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/*
 * 2021.12.09 daily algo/commit
 */

public class boj_16937 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = 0; // 스티커 수
		
		int H = sc.nextInt();
		int W = sc.nextInt();
		int line_max = Math.max(H, W);
		int line_min = Math.min(H, W);
		
		int N = sc.nextInt();
		int[][] stickers = new int[N][2];
		for(int i=0; i<N; i++) {
			int R = sc.nextInt();
			int C = sc.nextInt();
			stickers[i][0] = Math.max(R, C);
			stickers[i][1] = Math.min(R, C);
		}
		
		Arrays.sort(stickers, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[0] - o1[0];
			};
		});
		
		int area = 0;
		int max = 0;
		int length = 0;
//		loop: 
		for(int i=0; i<N-1; i++) {
			if((stickers[i][0] > H && stickers[i][0] > W) || (stickers[i][1] > H && stickers[i][1] > W)) continue; // 스티커가 모눈종이를 벗어날 때
			length = line_min - stickers[i][1];
			
			System.out.println(Arrays.deepToString(stickers));
			area = stickers[i][0] * stickers[i][1];
			System.out.println(H+" "+W+" "+length);
			System.out.println(i+" "+area);
			for(int j=i+1; j<N; j++) {
				if(stickers[j][0] > length || stickers[j][1] > length) continue;
				area += stickers[j][0] * stickers[j][1];
				System.out.println(j+" "+area);
				if(max < area) max = area;
				if(H >= W) {
					length = W;
				}
				else {
					length = H;
				}
				break;
			}
		}
		
		System.out.println(max);
		
		sc.close();
	}

}

강의내용

✔️스티커는 2개만 붙인다. (최대한 많은 스티커를 붙이는 것이 아님)

✔️붙여진 넓이의 최댓값을 구하는 것

✔️시간 복잡도 : N^2(스티커 2개 고름) x 2^2(각각 회전 함/안함) x 2(스티커 가로로 나열or 세로로 나열)
가장 최대의 경우가 8만개 이므로 모든 경우를 해보는 것이 가능하다.

• R1 + R2 <= H
• max(C1, C2) <= W

✔️정확한 경우의 수는 nC2

✍🏻내 코드3 + 강의

package BOJ;

import java.util.Scanner;

/*
 * 2021.12.09 daily algo/commit
 */

public class boj_16937 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int H = sc.nextInt();
		int W = sc.nextInt();
		
		int N = sc.nextInt();
		int[][] stickers = new int[N][2];
		for(int i=0; i<N; i++) {
			stickers[i][0] = sc.nextInt();
			stickers[i][1] = sc.nextInt();
		}
		
		int sum = 0; // 넓이 합
		int max = 0; // 최대 넓이
		for(int i=0; i<N-1; i++) {
			for(int j=i+1; j<N; j++) {
				if(stickers[i][0] + stickers[j][0] <= H && Math.max(stickers[i][1], stickers[j][1]) <= W ||
						stickers[i][0] + stickers[j][0] <= W && Math.max(stickers[i][1], stickers[j][1]) <= H) {
					sum = stickers[i][0] * stickers[i][1] + stickers[j][0] * stickers[j][1];
				}
				else if(stickers[i][0] + stickers[j][1] <= H && Math.max(stickers[i][1], stickers[j][0]) <= W ||
						stickers[i][0] + stickers[j][1] <= W && Math.max(stickers[i][1], stickers[j][0]) <= H) {
					sum = stickers[i][0] * stickers[i][1] + stickers[j][0] * stickers[j][1];
				}
				else if(stickers[i][1] + stickers[j][0] <= H && Math.max(stickers[i][0], stickers[j][1]) <= W ||
						stickers[i][1] + stickers[j][0] <= W && Math.max(stickers[i][0], stickers[j][1]) <= H) {
					sum = stickers[i][0] * stickers[i][1] + stickers[j][0] * stickers[j][1];
				}
				else if(stickers[i][1] + stickers[j][1] <= H && Math.max(stickers[i][0], stickers[j][0]) <= W ||
						stickers[i][1] + stickers[j][1] <= W && Math.max(stickers[i][0], stickers[j][0]) <= H) {
					sum = stickers[i][0] * stickers[i][1] + stickers[j][0] * stickers[j][1];
				}
				if(max < sum) max = sum;
			}
		}
		
		System.out.println(max);
		sc.close();
	}

}

💡H와 W의 경우가 반대인 경우를 모두 생각하니 if 조건줄이 너무 길어졌는데 어떻게 하면 줄일 수 있을 지 고민해봐야겠다.
💡1년전에 풀었던 풀이는 8가지 경우를 모두 풀어썼는데 지금보다 메모리가 시간이 더 적게 걸렸다.