CareerCup 귀속 및 동적 기획 Q9.10 최대 높이 쌓기 상자

n개의 상자를 한 무더기 드릴게요.상자는 뒤집을 수 없으며, 상자를 쌓을 때, 아래 상자의 너비, 높이, 깊이는 반드시 위의 상자보다 커야 한다.하나의 방법을 실현하여 가장 높은 한 무더기의 상자를 꺼내고 상자의 높이는 각 상자의 높이의 총계이다.
분석: 귀환, 자문제는 어떤 상자를 밑바닥으로 하는 높이가 가장 높은 탑으로 밑바닥을 확정한 후 밑에 놓을 수 있는 상자를 찾아 다시 귀환하여 자문제를 구한다.
주의: 중복자 문제가 존재하므로 동적 기획을 고려하고 표로 중간 결과를 기록하여 나중에 조회할 수 있도록 한다.

package cci;

import java.util.ArrayList;

class Box{
	int height;
	int width;
	int depth;
	public Box(int height, int width, int depth){
		this.height=height;
		this.width=width;
		this.depth = depth;
	}
	public boolean canBeAbove(Box box){
		if(box==null)
			return true;
		if(height<box.height && width<box.width && depth<box.depth)
			return true;
		return false;
	}	
	public void print(){
		System.out.println(height+" "+width+" "+depth);
	}
}

public class CCI_9_10 {
	
	public static ArrayList<Box> maxBoxTower(Box[] boxes){
		return maxBoxTower(boxes, null);
	}
	private static ArrayList<Box> maxBoxTower(Box[] boxes, Box bottom){
		ArrayList<Box> maxTower = new ArrayList<Box>();
		int maxHeight = 0;
		//       
		for(int i=0; i<boxes.length; i++){
			//      bottom    
			if(boxes[i].canBeAbove(bottom)){
				//             （  ，            ，            ）
				ArrayList<Box> newTower = maxBoxTower(boxes, boxes[i]);
				//               
				int newHeight = calTowerHeight(newTower);
				if(newHeight>maxHeight){
					maxHeight = newHeight;
					maxTower = newTower;// boxes[i]      
				}
			}
		}
		if(bottom != null){
			maxTower.add(0, bottom);
		}
		return maxTower;
	}
	private static int calTowerHeight(ArrayList<Box> tower){
		int height=0;
		for(Box box : tower){
			height += box.height;
		}
		return height;
	}
	
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Box[] boxes = new Box[3];
		boxes[0] = new Box(1,1,1);
		boxes[1] = new Box(2,2,2);
		boxes[2] = new Box(3,3,3);
		ArrayList<Box> result = maxBoxTower(boxes);
		for(Box item : result){
			item.print();
		}
	}
}