[백준 / BOJ] 10881 프로도의 선물 포장 (Java)

문제

출처 : https://www.acmicpc.net/problem/10881

10881번: 프로도의 선물 포장

프로도는 네오에게 줄 생일 선물을 세 개 샀다.

선물 세 게를 N*M 크기의 상자에 적절히 담을려고한다.

(모든 상자의 면은 서로 수평되어야 하며, 상자는 90도 회전가능하다.)

이때, 상자의 사이즈를 가장 작게하는 프로그램을 구하는 문제다.

---

풀이

상자가 최대 3개이고, 테스트케이스도 10,000이므로 완전탐색으로 풀수있는 문제다.

다만, 구현이 까다로웠는데, 상자의 크기가 제각각이라, 어디에 연결해야 최적일지 일일이 가로 세로면을 확인하는 방법은 매우매우 어렵다고 생각했다.

 

구현을 쉽게하기위해 다음 아이디어로 문제를 풀었다.

 

위에서 말한것처럼, 어디에 연결해야 최적일지 일일이 가로 세로를 확인하는 방법은 어렵다.

따라서, 상자의 가로 세로중 연결할수있는 남은 부분을 확인하지않고, 임의의 상자 2개를 적절히 연결(90도, 수평, 수직)한다.

그러면 상자 list에는 연결된상자 1개, 상자 1개 이렇게 총 2개의 상자가 남게된다.

이후, 상자 2개를 적절히(수평, 수직) 연결한 값중 최솟값을 가져오면 답이된다.

 

위 알고리즘중, 핵심은 우선 임의의 상자 2개를 연결하는 것이다.

이렇게 구현할 경우 (가로, 세로)중 남은면을 확인할 것 없이, 모든경우의 수를 봐줄수있으므로, 더욱 쉽게 구현할수있다.

 

주요 소스코드

(하드코딩에 빌더패턴 연습하느라 코드가 좀 더럽다.)

	private int packaging(int idx, int cnt, ArrayList<Rect> list, boolean[] check, Rect rect){
		int ret = 987654321;
		if(cnt == 2){
			Rect remain = null;
			for(int i = 0; i < 3; i++)
				if(!check[i]) remain = list.get(i);
			// 수평
			Rect ansWRect = new Rect.Builder()
				.width(remain.width+rect.width)
				.height(Math.max(remain.height, rect.height))
				.build();
			// 수직
			Rect ansHRect = new Rect.Builder()
				.width(Math.max(remain.width, rect.width))
				.height(remain.height+rect.height)
				.build();
			return Math.min(ansWRect.width*ansWRect.height, ansHRect.width*ansHRect.height);
		}
		for(int i = idx; i < 3; i++){
			if(check[i]) continue;
			check[i] = true;
			for(int dir = 0; dir < 2; dir++){
				Rect nextWRect = null;
				Rect nextHRect = null;
				if(dir == 0){
					// 정방향 수평 연결
					nextWRect = new Rect.Builder()
						.width(rect.width+list.get(i).width)
						.height(Math.max(rect.height, list.get(i).height))
						.build();
					// 정방향 수직 연결
					nextHRect = new Rect.Builder()
						.width(Math.max(rect.width, list.get(i).width))
						.height(rect.height+list.get(i).height)
						.build();
				}
				if(dir == 1){
					// 90도 회전 수평 연결
					nextWRect = new Rect.Builder()
						.width(rect.width+list.get(i).height)
						.height(Math.max(rect.height, list.get(i).width))
						.build();
					// 90도 회전 수직 연결
					nextHRect = new Rect.Builder()
						.width(Math.max(rect.width,list.get(i).height))
						.height(rect.height+list.get(i).width)
						.build();
				}
				ret = Math.min(ret, packaging(i+1, cnt+1, list, check, nextWRect));
				ret = Math.min(ret, packaging(i+1, cnt+1, list, check, nextHRect));
			}
			check[i] = false;
		}
		return ret;
	}

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/10881%20%ED%94%84%EB%A1%9C%EB%8F%84%EC%9D%98%20%EC%84%A0%EB%AC%BC%20%ED%8F%AC%EC%9E%A5/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃