[백준] 2628 종이자르기

1. 문제

www.acmicpc.net/problem/2628

2628번: 종이자르기

2. 접근방법

가로로 자를지 세로로 자를지와

자를 위치가 입력으로 들어온다.

 

나는 길이를 가지고 접근해 봤다.

 

처음 주어지는 길이를 Arraylist에 저장한다.

가로 : [10]

세로 : [8]

 

처음 가로로 3의 길이를 자르면

세로 길이가 [3,5] 가 되고

 

다음 세로로 4의 길이를 자르면

가로 길이가 [4 , 6] 이 된다.

 

그 다음 가로로 2의 길이를 자르면

세로가 [2 , 1 , 5] 가  된다.

 

다 자르고 나면

가로 : [4 , 6]

세로 : [2 , 1 , 5]

이므로 각 각 가로와 세로를 곱하면 모든 사각형의 넓이를 구할 수 있다.

그 중 가장 큰 넓이를 구하면 된다.

3. 자바 코드

package Silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class P2628종이자르기 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		List<Integer> garo = new ArrayList<Integer>();
		List<Integer> sero = new ArrayList<Integer>();
		
		
		garo.add(Integer.parseInt(st.nextToken()));
		sero.add(Integer.parseInt(st.nextToken()));
		
		int N = Integer.parseInt(br.readLine());
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			int what = Integer.parseInt(st.nextToken());
			int where = Integer.parseInt(st.nextToken());
			if(what == 0) { // 가로
				int index;
				for(index = 0  ; where - sero.get(index)>0 ; index++ ) {
					where -= sero.get(index);
				}
				int temp = sero.remove(index);
				sero.add(index,temp-where);
				sero.add(index,where);
			}
			else { // 세로
				int index;
				for(index = 0  ; where - garo.get(index)>0 ; index++ ) {
					where -= garo.get(index);
				}
				int temp = garo.remove(index);
				garo.add(index,temp-where);
				garo.add(index,where);
			}
		}
		int max = 0;
		for(int i : garo) {
			for(int j : sero)
				max = Math.max(i*j, max);
		}
		System.out.println(max);
		
		
		
	}

}

4. 마치며

길이로 잘라내는 아이디어만 잘내면 쉽게 풀리는 문제였다.