BOJ_2628_종이자르기_JAVA
문제 : 종이자르기
링크 : BOJ_2628_종이자르기
접근 방식
직사각형 모양의 종이를 가로, 세로로 자른 후 잘라진 사각형 중 가장 큰 사각형을 찾아야한다. 나는 이 문제를 링크드리스트를 이용해서 풀려고 했다.
링크드리스트를 2개 생성 (가로, 세로)
가로로 자르는 경우
세로리스트에 들어있는 값과 비교해서 해당 값보다 작다면 기존 리스트의 해당 값을 제거하고 그 위치에 K, 해당 값 - K를 순서대로 넣는다. 값-K와 K를 순서대로 넣으면 된다.
세로리스트에 들어있는 값과 비교해서 해당 값보다 크다면 주어진 K에 해당 값을 빼고 다음 값으로 넘어간다.
세로로 자르는 경우
가로로 자르는 경우와 같은 방법이다. 가로 리스트에 들어있는 값에 위와 동일한 로직을 수행하도록 한다.
모든 과정을 거친 리스트를 내림차순 정렬하면 잘린 종이의 가로변, 세로변 중 가장 큰 값이 0번 위치에 오게 된다. 둘을 곱하면 문제가 요구하는 답을 얻을 수 있다.
풀이 방법
-
사각형의 가로, 세로 정보를 읽어와 2개의 링크드리스트의 초기 값으로 집어넣는다.
-
주어진 자르는 회수만큼 반복한다.
-
표준입력으로 주어지는 값(가로세로 여부, 자르는 번호)을 읽어들여 가로로 자르는지, 세로로 자르는지 먼저 구분한다.
-
현재 리스트의 길이만큼 반복하는데, 자르는 번호가 현재 리스트의 크기보다 작다면 기존 리스트의 값을 꺼내고, 리스트의 값에서 자르는 번호만큼 뺄셈하여 2개의 리스트를 다시 리스트에 add시켜준다.
-
만약 자르는 번호가 현재 리스트의 값 보다 크다면, 자르는 번호에서 현재 리스트의 값만큼 뺄셈해준다. 그 후 다음 리스트의 값에서 같은 내용을 반복한다.
-
세로로 자를 경우도 동일하게 수행한다.
-
모든 반복이 끝나고 난 후 두개의 리스트를 내림차순정렬한다.
-
각각 내림차순 정렬한 리스트의 0번째 값을 서로 곱해서 출력해준다.
소스 코드
import java.awt.List;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class BOJ_2628_종이자르기 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine()," ");
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
// 세로리스트
LinkedList<Integer> list1 = new LinkedList<>();
// 가로리스트
LinkedList<Integer> list2 = new LinkedList<>();
list1.add(N);
list2.add(M);
int R = Integer.parseInt(in.readLine());
for(int i=0;i<R;i++) {
st = new StringTokenizer(in.readLine()," ");
//가로, 세로 여부
int D = Integer.parseInt(st.nextToken());
// 길이
int L = Integer.parseInt(st.nextToken());
// 가로로 자를 경우
if(D == 0) {
// 리스트 길이만큼 반복
for(int j=0,n=list1.size();j<n;j++) {
if(list1.get(j) > L) {
int temp = list1.remove(j) - L;
list1.add(j,temp);
list1.add(j,L);
break;
}else {
L = L - list1.get(j);
}
}
// 세로로 자를 경우
}else {
for(int j=0,n=list2.size();j<n;j++) {
if(list2.get(j) > L) {
int temp = list2.remove(j) - L;
list2.add(j,temp);
list2.add(j,L);
break;
}else {
L = L - list2.get(j);
}
}
}
}
System.out.println(list1);
System.out.println(list2);
Collections.sort(list1,Collections.reverseOrder());
Collections.sort(list2,Collections.reverseOrder());
System.out.println(list1.get(0)*list2.get(0));
}
}