[BOJ][JAVA] 두 스티커-16937-완전탐색

📌 문제

백준 두 스티커 | 실버 3

#구현 #브루트포스 알고리즘 #기하학 #많은 조건 분기

https://www.acmicpc.net/problem/16937

 

 

📌 문제 탐색하기

• 입력값
  • H * W 크기 모눈종이 스티커 N개
• 출력값
  • 스티커가 붙여진 넓이의 최댓값
• 모눈종이는 1*1 크기칸
• 스티커가 접하는 것이 가능하고, 90도 회전시키는 것 가능
• 모눈종이를 벗어나는 건 불가능

 

 

📌 알고리즘 설정

• 문제에서 모든 입력값들이 100이하이므로, 최대 사이즈가 10000까지만 나올 예정
• 스티커는 2개를 골라야하므로, n이 100이니까 100 * 99 = 9900개의 경우의 수가 나올 예정
• 이때, 스티커가 모눈종이 H*W 칸에 또 들어가야하므로 이 경우를 세야함
  • 스티커는 회전이 가능하다고 했으므로, 총 4가지 방안으로 스티커 부착 가능
    • 수직, 수직
    • 수평, 수직
    • 수직, 수평
    • 수평,수평
  • 이를 가로로 이어붙이는 경우, 세로로 이어붙이는 경우 2가지 존재

⇒ 총 9900가지의 경우의 수 & 각 경우에 대해 O(1)의 시간복잡도 (8가지) = 완전탐색 가능

 

 

📌 시뮬레이션 

A, B 2가지의 스티커를 골랐을 경우, 모눈종이에 붙일 수 있는지 아닌지 확인해야함

• 스티커는 총 4가지의 경우의 수로 붙일 수 있음
  • 수직, 수직
  • 수평, 수직
  • 수직, 수평
  • 수평, 수평
  ⇒ 수직 (있는 그대로), 수평 (스티커를 90도 회전)
• 어떻게 붙일지 결정 후, 모눈종이에 스티커를 붙일 수 있는지 판단
  • 가로로 이어지게
    • 두 가로의 길이의 합은 H보다 작거나 같아야하고
    • 두 세로 중 최대 길이는 W보다 작거나 같아야함
  • 세로로 이어지게
    • 두 가로 중 최대 길이는 H보다 작거나 같아야하고
    • 두 세로의 길이의 합은 W보다 작거나 같아야함

example)

10 9
4
2 3
1 1
5 10
9 11

→ 이 중에서 23, 510으로 예시를 잡을 경우

• 수직,수직,가로 ⇒ 가로 길이 합 7 ≤ 10 & 세로 max(10) ≤ 10 이므로 통과
• 현재 탐색 중인 정답보다, 이 스티커의 크기가 클 경우 정답값을 업데이트
  • 만약, 수직, 수직, 세로 ⇒ 세로 길이 합 13 ≥ 10이므로 fail..

정리하자면)

• N가지 스티커 중 2가지를 선택하는 경우의 수 구하기
• 각 경우에 수평, 수직, 가로, 세로 총 8가지의 케이스에 대해 모눈종이에 붙일 수 있는지 확인
• 그 후 가능하다면 정답과 비교해 더 큰값으로 업데이트

 

📌 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class q16937_silver3 {
    static int h, w, size = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        List<Size> list = new ArrayList<Size>();

        st = new StringTokenizer(br.readLine());
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        size = h * w;

        int answer = 0;

        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if (r * c <= size) {
                list.add(new Size(r, c, r * c));
            }
        }

        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                Size s1 = list.get(i);
                Size s2 = list.get(j);

                int tmpSize = s1.size + s2.size;

                //수평, 수평, 가로
                if(s1.r + s2.r <= h && Math.max(s1.c, s2.c) <= w){
                    answer = Math.max(answer, tmpSize);
                }
                //수평, 수평, 세로
                if(Math.max(s1.r, s2.r) <= h && s1.c + s2.c <= w){
                    answer = Math.max(answer, tmpSize);
                }

                //수직, 수평, 가로
                if(s1.c + s2.r <= h && Math.max(s1.r, s2.c) <= w){
                    answer = Math.max(answer, tmpSize);
                }
                //수직, 수평, 세로
                if(Math.max(s1.c, s2.r) <= h && s1.r + s2.c <= w){
                    answer = Math.max(answer, tmpSize);
                }

                //수평, 수직, 가로
                if(s1.r + s2.c <= h && Math.max(s1.c, s2.r) <= w){
                    answer = Math.max(answer, tmpSize);
                }
                //수평, 수직, 세로
                if(Math.max(s1.r, s2.c) <= h && s1.c + s2.r <= w){
                    answer = Math.max(answer, tmpSize);
                }

                //수직, 수직, 가로
                if(s1.c + s2.c <= h && Math.max(s1.r, s2.r) <= w){
                    answer = Math.max(answer, tmpSize);
                }
                //수직, 수직, 세로
                if(Math.max(s1.c, s2.c) <= h && s1.r + s2.r <= w){
                    answer = Math.max(answer, tmpSize);
                }

            }
        }

        System.out.println(answer);

    }
}

class Size {
    int r;
    int c;
    int size;

    public Size(int r, int c, int size) {
        this.r = r;
        this.c = c;
        this.size = size;
    }
}