[BOJ] 16937: 두 스티커 (JAVA)

문제

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

 

여담

어떻게 풀지 감이 안 잡혀서 다른 분의 풀이를 참고했다. 양심상 풀이를 참고하더라도 완전히 코드를 따라 치지 않으려고 하기 때문에, 풀이 방식을 토대로 다시 생각하고 문제를 풀었다.

 

풀이를 보기 전에는 엄청 막막해서 풀기 싫었는데, 풀이를 보고 난 뒤에는 생각보다 쉽게 풀 수 있어서 다시 집중해서 풀었다. 이러한 일이 종종 있었는데 "어 이거 좀 어려운데..?"라는 생각이 들면 내가 풀지 못한다고 생각하고 더 이상 생각을 안 하는 것 같다. 진짜 안 좋은 습관인데... ㅎㅏ.. 진짜 6월 내로 꼭 고치자

 

풀이

이 문제에서 가장 중요한 포인트는 다음과 같다.

• 두 개의 스티커만 붙일 수 있으며, 두 스티커가 겹치면 안된다.
• 스티커는 모눈종이를 벗어나면 안된다.
• 스티커를 90도 회전해서 붙일 수 있다.

 

문제에서 주어지는 변수들의 범위가 크지 않기 때문에 완전 탐색으로 풀 수 있다. 따라서 스티커를 하나씩 다 확인해서 최대 넓이를 계산하면 된다. 대략적인 진행 과정은 다음과 같으며, 자세한 내용은 아래의 예시와 코드를 참고하면 된다.

1. 첫 번째로 붙일 스티커 선택하기
2. 두 번째로 붙일 스티커 선택하기
3. 두 스티커들의 넓이를 계산하기
   • 만약 이미 저장된 최대 넓이보다 크다면 갱신하기

 

예시

10 × 9 모눈종이에 2 × 3 스티커를 붙이는 경우를 살펴보자. (예제 입력 2)

 

2 × 3 스티커를 그대로 붙이는 경우

스티커를 붙일 수 있는 공간은 10 × 6, 8 × 9이다. 따라서 해당 공간 안에 들어가는 스티커들을 찾아서 넓이를 계산하면 된다. 이때, 두 번째로 붙이는 스티커도 그대로 붙이는 경우와 90도로 회전해서 붙이는 방법 총 2가지를 고려해야 한다.

• 1 × 1 스티커 - 가능
  • 넓이 = 6 + 1 = 7
• 5 × 10 스티커 - 불가능
• 10 × 5 스티커 - 가능 (5 × 10 스티커를 90도 회전한 것)
  • 넓이 = 6 + 50 = 56
• 9 × 11 스티커 - 불가능
• 11 × 9 스티커 - 불가능 (9 × 11 스티커를 90도 회전한 것)

 

2 × 3 스티커를 90도 회전해서 붙이는 경우

스티커를 붙일 수 있는 남은 공간은 10 × 7, 7 × 9이다. 따라서 해당 공간 안에 붙일 수 있는 스티커들을 찾아서 넓이를 계산하면 된다.

• 1 × 1 스티커 - 가능
  • 넓이 = 6 + 1 = 7
• 5 × 10 스티커 - 불가능
• 10 × 5 스티커 - 가능 (5 × 10 스티커를 90도 회전한 것)
  • 넓이 = 6 + 50 = 56
• 9 × 11 스티커 - 불가능
• 11 × 9 스티커 - 불가능 (9 × 11 스티커를 90도 회전한 것)

 

따라서 두 스티커가 붙여진 넓이의 최댓값은 56이다.

 

코드

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

public class Main {
    static int H, W, N;
    static int ans = 0;
    static Sticker[] stickers;
    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());
        N = Integer.parseInt(br.readLine());
        stickers = new Sticker[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            stickers[i] = new Sticker(h, w);
        }
        firstSticker();
        System.out.println(ans);
    }

    // 스티커 1개 붙이기
    public static void firstSticker() {
        for (int i = 0; i < N; i++) {
            Sticker sticker = stickers[i];
            int h = sticker.h, w = sticker.w;
            // 원래 모양대로 붙이기
            if (h <= H && w <= W) { // 해당 스티커를 붙일 수 있는 경우
                secondSticker(H - h, W - w, i + 1, h * w);
            }

            // 90도 회전해서 붙이기
            if (h <= W && w <= H) { // 해당 스티커를 붙일 수 있는 경우
                secondSticker(H - w, W - h, i + 1, h * w);
            }
        }
    }

    // 스티커 2개 붙이기
    public static void secondSticker(int newH, int newW, int idx, int size) {
        for (int i = idx; i < N; i++) {
            Sticker sticker = stickers[i];
            int h = sticker.h, w = sticker.w;
            // 원래 모양대로 붙이기
            if ((h <= newH && w <= W) || (h <= H && w <= newW)) {
                ans = Math.max(ans, size + h * w);
            }

            // 90도 회전해서 붙이기
            h = sticker.w;
            w = sticker.h;
            if ((h <= newH && w <= W) || (h <= H && w <= newW)) {
                ans = Math.max(ans, size + h * w);
            }
        }
    }

    static class Sticker {
        int h, w;

        public Sticker(int h, int w) {
            this.h = h;
            this.w = w;
        }
    }
}

---

참고

https://tussle.tistory.com/835