[java][boj][s5] 2628. 종이자르기

2628번: 종이자르기

문제

아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.

<그림 1>

점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다.

<그림 2>

입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.

입력

첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.

출력

첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.

풀이

/*
 * 1. 종이의 가로N와 세로M의 길이
 * 2. 칼로 잘라야 하는 점선의 개수 K
 * 3. 가로0, 세로1과 점선 번호
 * 4. 출력: 가장 큰 종이 조각의 넓이
 * 
 * >> 2차원 배열에 숫자 넣기
 * >> 잘린 줄에 1 넣기
 * >> 0을 세다가 1이 나오면
 * 
 * >> 가로(세로) 길이에서 가로(세로)로 자르는 숫자를 빼서 선 세 개 구하기
 * >> 선 세 개 중 가장 큰 값 구해서 곱하기
 * 
 * >> 리스트 써서 가로 길이와 세로 길이 각각 넣기
 * >> 리스트 크기만큼 for문 돌려서 인덱스+1 - 인덱스 값 계산하기 => 선의 길이 구하기
 * >> 선 길이 중 가장 큰 것 구해서 곱하기
 * 
 * >> 배열 써서 하기
 */

첫 번째가 틀린 이유는 단순히 숫자가 선인 게 아니라 숫자 사이의 차이가 선이 되기 때문에 틀렸다 배열에 숫자를 모두 넣은 뒤 오름차순으로 정렬해서 각각의 차이를 구한 뒤 가장 큰 숫자 두개를 곱했다

코드

package im형필수문제;

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

public class s5_2628_종이자르기 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int K = Integer.parseInt(br.readLine());
		
		int[] nNum = new int[K+1];
		int[] mNum = new int[K+1];
		
		int nMax = 0;
		int mMax = 0;

		nNum[0] = N;
		mNum[0] = M;
		
		for(int i = 1; i<=K; i++) {
			st = new StringTokenizer(br.readLine());
			int dir = Integer.parseInt(st.nextToken());
			int num = Integer.parseInt(st.nextToken());
			if(dir == 1) {
				nNum[i] = num;
			} else {
				mNum[i] = num;
			}
		}
		
		Arrays.sort(nNum);
		Arrays.sort(mNum);

		for(int i = 1; i<nNum.length; i++) {
			int len = nNum[i] - nNum[i-1];
			nMax = Math.max(nMax, len);
		}
		for(int i = 1; i<mNum.length; i++) {
			int len = mNum[i] - mNum[i-1];
			mMax = Math.max(mMax, len);
		}
		System.out.println(nMax*mMax);
	}
}

결과

 

#자바 #java #boj #백준 #알고리즘