백준 2628 <종이자르기>

IM 대비 문제 치고는 많이 생각할 점이 있는 문제였다.

이 문제의 핵심은 자른 색종이의 가로와 세로가 가장 큰 길이를 찾는 것이다.

 

문제 풀이

1. 가로 세로 가장 긴 길이를 탐색하기 위해 각각의 ArrayList에 넣고 정렬을 했다. 
2. 투 포인터라는 개념을 기준으로 시작점을 0으로 잡고 하나씩 꺼내 사이의 간격을 비교해준다.
3. 이렇게 가로 세로가 구해지면 곱해준다.

시작점을 0 으로 잡고 다음 지점과 간격을 비교하고 시작점을 이동하고 그렇게 끝까지 계산하면 가장 긴 길이를 구할 수 있다.! 마지막에는 마지막 자른 위치와 총길이를 빼주는 계산이 필수!!

예를 들어 세로 부분 3이 마지막이므로 총길이 8에서 3을 빼주는 것도 포함!

 

 

1번 순서 ArrayList에 넣고 정렬!

위에 부분이 가로 아래부분이 세로

 

 

전체 코드

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

public class Main{

	static ArrayList<Integer> a,b;
	static int width,height,num;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader (System.in));
		a=new ArrayList<Integer>();
		b=new ArrayList<Integer>();
		StringTokenizer st=new StringTokenizer(br.readLine());
		width=Integer.parseInt(st.nextToken());
		height=Integer.parseInt(st.nextToken());
		num=Integer.parseInt(br.readLine());
		for(int i=0;i<num;i++) {
			st=new StringTokenizer(br.readLine());
			int where=Integer.parseInt(st.nextToken());
			int k=Integer.parseInt(st.nextToken());
			if(where==1) {
				a.add(k);
			}else {
				b.add(k);
			}
		}
		Collections.sort(a);
		Collections.sort(b);
		int w=0;
		int start=0;
		for(int i=0;i<a.size();i++) {
			if(a.get(i)-start>w) {
				w=a.get(i)-start;
			}
			start=a.get(i);
		}
		if(width-start>w) {
			w=width-start;
		}
		int h=0;
		start=0;
		for(int i=0;i<b.size();i++) {
			if(b.get(i)-start>h) {
				h=b.get(i)-start;
			}
			start=b.get(i);
		}
		if(height-start>h) {
			h=height-start;
		}
		System.out.println(h*w);
	}


}