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

문제 링크

16937번: 두 스티커

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 스티커는 2개를 붙일 때 두 스티커의 최대 넓이 합을 구해야합니다.

2. 스티커는 90도로 회전이 가능합니다.

3. 스티커는 겹치면 안되고 모눈종이에 벗어나면 안됩니다.

4. 스티커를 2개 붙일 수 없는 경우에는 0을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 모든 스티커에 대하여 2개를 붙이는 경우를 탐색하여 최대 넓이를 구합니다.

 

3. 최대 넓이를 구하지 못하면 0, 구하였다면 최대 넓이를 결과로 출력합니다.

 

 

스티커 붙일 때

 

5 × 5 모눈종이가 주어지고 스티커를 붙이려고하면

3 × 2 스티커1, 3 × 3 스티커2가 존재한다고 할 때

3 × 2 스티커를 먼저 모눈종이에 붙인다고 하면

스티커1	스티커1
스티커1	스티커1
스티커1	스티커1

※스티커를 1개 먼저 붙일 때 항상 (0, 0)을 기준으로 붙일 것입니다. 

※다음 스티커를 붙일 수 있는 최대의 칸을 남기기 위해서입니다.

 

다음 스티커를 붙일 수 있는 공간은

스티커1	스티커1	1	1	1
스티커1	스티커1	1	1	1
스티커1	스티커1	1	1	1
		1	1	1
		1	1	1

스티커1	스티커1
스티커1	스티커1
스티커1	스티커1
2	2	2	2	2
2	2	2	2	2

 

1의 영역

5 × 3

3 × 3스티커를 붙일 수 있습니다.

 

2의 영역

2 × 5

 

스티커1	스티커1	스티커2	스티커2	스티커2
스티커1	스티커1	스티커2	스티커2	스티커2
스티커1	스티커1	스티커2	스티커2	스티커2

 

 

예제입력 1.

 

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

 

H = 2

W = 2

N = 2

스티커1 : 1 × 2

스티커2 : 2 × 1

 

2.  모든 스티커에 대하여 2개를 붙이는 경우를 탐색하여 최대 넓이를 구합니다.

 

스티커 1을 붙이기

 

스티커1	스티커1

 

스티커2를 붙일수 있는 영역

스티커1	스티커1
1	1

1의 영역 : 1 × 2

스티커 2  : 2 × 1 붙일 수가 없습니다.

 

90도 회전 진행

스티커 2 : 1 × 2는 붙일 수 있습니다.

 

스티커1	스티커1
스티커2	스티커2

모든 모눈 종이를 채웠기 때문에 최대 넓이가 됩니다.

 

3. 최대 넓이를 구하지 못하면 0, 구하였다면 최대 넓이를 결과로 출력합니다.

 

최대 넓이 4를 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 입력된 값을 띄어쓰기 기준 나누었습니다.
• 값을 입력받을 때 모눈 종이에 붙일 수 없는 스티커는 저장하지 않습니다.
• cal을 실행하여 스티커를 붙이는 모든 경우를 진행하여 최대 넓이를 구합니다.
• 최대 넓이가 존재하지 않으면 0, 존재하면 최대 넓이를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 모든 스티커를 1번째 스티커로 (0,0)에 그대로 및 회전하여 붙여보는 것을 진행합니다.
• secondSticker 1번째 스티커를 붙이고 남은 영역에 2번째 스티커를 그대로 및 회전하여 붙여봅니다.
• secondSticker 2번째 스티커를 붙였을 때 최대 넓이인지 확인합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    //스티커 정보 관련 클래스
    static class sticker{
        int h, w;
        public sticker(int h, int w) {
            this.h = h;
            this.w = w;
        }
    }
    static int H,W,N, answer = 0;
    static ArrayList<sticker> info = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(br.readLine());
        //입력값 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            //모눈종이에 붙이지 못하는 스티커이면 넘기기
            if((h > H && h > W) || (w > W && w > H))
                continue;
            info.add(new sticker(h, w));
        }
        cal();	//모든 스티커 경우 구하기
        bw.write(answer + "");	//최대 넓이 BufferedWriter 저장
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
    //모든 스티커 붙이는 경우 구하는 함수
    static void cal(){
        //1번째 스티커 (0,0)기준으로 붙이기
        for(int i=0;i<info.size();i++){
            sticker cur = info.get(i);
            int size = cur.h * cur.w;
            int tempH = H - cur.h;
            int tempW = W - cur.w;
            if(tempH>=0 && tempW>=0)	//1번째 스티커 붙이기 성공시
                secondSticker(i, tempH, tempW, size);

            //1번째 스티커 회전해서 붙여보기
            tempH = H - cur.w;
            tempW = W - cur.h;
            if(tempH>=0 && tempW>=0)	//회전한 1번째 스티커 붙이기 성공시
                secondSticker(i, tempH, tempW, size);
        }
    }
    //두 번째 스티커 붙이는 함수
    static void secondSticker(int index, int h, int w, int size){
        int secondSize = 0;
        for(int i=index+1;i<info.size();i++){
            sticker cur = info.get(i);
            int tempSize = cur.h * cur.w;	//2번째 스티커 넓이
            //모눈 종이에 영역에 2번째 스티커를 그대로 및 회전하여 붙여볼 때 성공시
            if((cur.h <= h && cur.w <= W) || (cur.h <= H && cur.w <= w)
                ||(cur.w <=h && cur.h <=W) || (cur.w <=H && cur.h <= w))
                secondSize = Math.max(secondSize, tempSize);
        }
        //두 번째 스티커 붙이기 성공할 때 최대 넓이 비교하기
        if(secondSize!=0)
            answer = Math.max(answer, size+secondSize);
    }

}