[백준/Java] 16937번 : 두 스티커

✏️ 문제 분석

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

HxW크기 격자에 R1xC1, R2xC2, ..., RnxCn 크기 스티커 중 2개를 붙일 때 (스티커 90도 회전 가능)

두 스티커가 붙여진 넓이의 최댓값은?

✏️ 구현 아이디어

격자에 두 스티커를 붙일 때 이렇게 네 가지 경우가 나온다.

같이 붙일 수 있다면 max값을 갱신하여 가장 넓은 값을 출력한다.

✏️ 시간 복잡도

스티커 100개 중 2개를 고르는 경우의 수는 100_P_2 = 100*99/2 = 4,950가지

스티커 한 개를 붙일 수 있는지 확인하는 로직은 O(2)이므로 시간 안에 연산 가능하다.

✏️ 알고리즘

모든 경우를 다 탐색하는 브루트포스를 사용한다.

✏️ 오답 노트

언급했던 네 가지 방법만 확인하면 안 된다.

 

반례 :

이 경우 90도 회전하면 스티커를 붙일 수 있다.

그래서 네 경우가 아니라 90도 회전한 경우를 추가해 8가지 경우를 고려해야 한다.

✏️ 코드 설계

1. 입력값 받기
2. sticker[]에서 두 개의 스티커를 꺼내서 isPossible로 확인
3. isPossible : s1, s2를 격자에 붙일 수 있는지 확인하는 함수
   1. 8가지 경우를 구현하여 HxW 격자 밖으로 스티커가 나가지 않는지 확인
   2. 스티커를 붙일 수 있으면 true 반환
   3. 가독성을 위해서 if문 나열함
4. max값을 갱신하여 가장 큰 값을 리턴

✏️ 정답 코드

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    static Sticker[] sticker;
    static int H, W, N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        sticker = new Sticker[N];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            sticker[i] = new Sticker(r, c);
        }

        int ans = 0;
		
        //스티커 2개 선택
        for(int i=0; i<N; i++){
           for(int j=i+1; j<N; j++){
               //붙일 수 있다면
               if(isPossible(sticker[i], sticker[j])){ 
                    //둘의 넓이 합 구해서
                    int totalArea = (sticker[i].c * sticker[i].r) + (sticker[j].c * sticker[j].r); 
                    //최댓값 갱신
                    ans = Math.max(ans, totalArea); 
               }
           }
        }
        System.out.println(ans);
    }

    //스티커 붙일 수 있는지 확인
    static boolean isPossible(Sticker s1, Sticker s2){
        int r1 = s1.r, c1 = s1.c;
        int r2 = s2.r, c2 = s2.c;

        boolean ret = false;
        
        int[][] tmp = {{H, W},{W, H}}; //격자 자체를 90도로 회전시킴
        for(int i=0; i<2; i++){
            int a = tmp[i][0];
            int b = tmp[i][1];
            
            //스티커 붙이는 4가지 조합 확인
            if(r1+r2<=a && Math.max(c1, c2)<=b) ret = true;
            if(r1+c2<=a && Math.max(c1, r2)<=b) ret = true;
            if(c1+r2<=a && Math.max(r1, c2)<=b) ret = true;
            if(c1+c2<=a && Math.max(r1, r2)<=b) ret = true;
        }

        return ret;
    }

}
class Sticker{
    int r, c;
    Sticker(int r, int c){
        this.r = r;
        this.c = c;
    }
}

✏️ Note

• 처음에 구현 아이디어를 떠올리기가 어려웠다. 
• 그리고 나 스스로 처음부터 모든 경우를 빠짐 없이 고려하기가 어렵다. 꼭 테케를 한 번 돌려서 우연히 반례가 발견되거나 질문 게시판에서 반례를 뒤져야 된다.
• 그냥 아직 구현 문제가 어려운 것 같다. 더 익숙해져야겠다.