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

📖 문제

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

 

 

 

💡  풀이 방식

• 브루트포스

1. 입력되는 정보들을 저장한다.

2. 모든 스티커들에서 2개를 붙이는 경우를 탐색해 최대 넓이를 구한다.

  - [스티커1 붙이기] 항상 (0,0)을 기준으로 붙인다. (목적: 다음 스티커를 붙일 수 있는 최대 칸을 남기기 위해)

3. 최대 넓이를 구하면 결과로 출력하고, 못 구하면 0을 결과로 출력한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int H,W,N;
    static List<Sticker> list = new ArrayList<>();
    static int answer = 0;
    
    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());
        
        while(N --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            // 모눈종이에 붙이지 못하는 스티커면 pass
            if((r > H && r > W) || (c > W && c > H))    continue;
            list.add(new Sticker(r, c));
        }
        
        solve();
        System.out.println(answer);
    }
    
    // 모든 스티커 붙이는 경우 구하는 함수
    private static void solve() {
        // [1번째 스티커] (0,0) 기준으로 붙이기
        for(int i = 0 ; i < list.size() ; i++) {
            Sticker now = list.get(i);
            int size = now.r * now.c;
            
            // 1. 1번 스티커 붙여보기
            int tmpR = H - now.r;
            int tmpC = W - now.c;
            
            // 1번 스티커 붙이기 성공 시
            if(tmpR >= 0 && tmpC >= 0)
                second(i, tmpR, tmpC, size);
                
            // 2. 1번 스티커 회전해서 붙여보기
            tmpR = H - now.c;
            tmpC = W - now.r;
            
            // 회전한 1번째 스티커 붙이기 성공 시
            if(tmpR >= 0 && tmpC >= 0)
                second(i, tmpR, tmpC, size);
        }
    }
    
    // [2번째 스티커] 붙이는 함수
    private static void second(int idx, int rr, int cc, int size) {
        int secondSize = 0;
        
        for(int i = idx + 1 ; i < list.size() ; i++) {
            Sticker now = list.get(i);
            
            int tmpSize = now.r * now.c;    // 2번째 스티커 넓이
            
            // 모눈 종이에 영역에 2번째 스티커를 그대로 / 회전해 붙여볼 때 성공 시
            if((now.r <= rr && now.c <= W) || (now.r <= H && now.c <= cc)
                || (now.c <= rr && now.r <= W) || (now.c <= H && now.r <= cc))
                secondSize = Math.max(secondSize, tmpSize);
        }
        
        // 2번째 스티커 붙이기 성공 시, 최대 넓이 비교하기
        if(secondSize != 0)
            answer = Math.max(answer, size + secondSize);
    }
}
 
class Sticker {
    int r, c;
    
    public Sticker(int r, int c) {
        this.r = r;
        this.c = c;
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

[BOJ] 두 스티커 - 16937번

 

---

💦 어려웠던 점

- 소문자 h인지 H인지 이걸 잘못 써서 한 20분 헤맸다고 한다... 그래서 그냥 변수명을 새롭게 rr, cc로 바꿔버렸다.

 

 

🧐 새로 알게 된 내용

- 범위 저렇게 설정하는 것,,,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[백준] code.plus(브루트 포스 Part 1,JAVA)16937번, 두 스티커