[BJ] 백준 2628 종이자르기 (JAVA)

문제

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

 

풀이 방법

우선 행과 열의 크기에 맞게 1차원 배열을 선언해줬다. 
그리고 그 배열에는 입력에 따라서 자른 점선 번호이면 1로 배열 값을 수정해줬다.
문제와 같은 예시로 설명을 하자면 

num	1	2	3	4	5	6	7	8	9
cutM	0	0	0	1	0	0	0	0	0

num	1	2	3	4	5	6	7
cutN	0	1	1	0	0	0	0

이런식으로 값이 들어가게 된다.
그 후 이제 각각 배열을 돌면서 temp 길이를 1을 하나씩 추가하다가 1을 만나면(잘려진 선을 만났으므로) 최대 길이와 비교해서 필요시 최대길이를 업데이트해주고 temp는 다시 0으로 설정해준다. (새로운 길이 시작)
열과 행을 같은 방법으로 구현 후, 각각의 max값을 곱해주는 식으로 구현했다.

 

제출 코드

package com.ssafy.im;

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

public class BJ_2628_종이자르기 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int M = Integer.parseInt(st.nextToken()); // 열
		int N = Integer.parseInt(st.nextToken()); // 행

		int[] cutM = new int[M + 1];
		int[] cutN = new int[N + 1];

		st = new StringTokenizer(br.readLine());
		int C = Integer.parseInt(st.nextToken()); // 점선 개수
		for (int i = 0; i < C; i++) {
			st = new StringTokenizer(br.readLine());
			int mode = Integer.parseInt(st.nextToken());
			int num = Integer.parseInt(st.nextToken());
			if (mode == 0) { // 가로로
				cutN[num] = 1; // 행 배열
			} else
				cutM[num] = 1;
		}
		int temp = 0;
		int maxN = 0;
		for (int i = 1; i <= N; i++) {
			temp++;
			if (cutN[i] == 1 || i == N) {
				maxN = Math.max(maxN, temp);
				temp = 0;
			}
		}
		temp = 0;
		int maxM = 0;
		for (int i = 1; i <= M; i++) {
			temp++;
			if (cutM[i] == 1 || i == M) {
				maxM = Math.max(maxM, temp);
				temp = 0;
			}
		}
		System.out.println(maxM * maxN);
	}

}