[BOJ] 두 스티커 - 16937번
🌠 "두 스티커" - 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가지 경우를 모두 풀어썼는데 지금보다 메모리가 시간이 더 적게 걸렸다.
Author And Source
이 문제에 관하여([BOJ] 두 스티커 - 16937번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bokiri409/BOJ-두-스티커-16937번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)