Pipe자르기

clone을 더 이상 사용하지 않고 temporary integer를 이용하여 해결하였으나 여전히 성능 개선이 되지 않는 중.

최악의 경우를 상정하면 분명 모든 경우를 다 체크해야 하는게 맞다. 

그러나 끝까지 체크해 보지 않더라도 중간 쯤에서 더 이상 계산하지 않아도 되는 지점에서 break를 걸 수 있으면 좋을 텐데.

일단 코드를 올린 후에 current maximum도 인자로 넘겨서 체크하는 것을 추가해서

끝까지 계산하지 않아도 되로록 수정해봐야겠다.

package defaultpackage;

import java.util.Arrays;

public class Pipe implements Cloneable{
	int[] longPipe;
	int[][] shortPipe=new int[2][];
	
	public Pipe(int[] longPipe, int[] shortPipe) {
		this.longPipe=longPipe;
		this.shortPipe[0]=shortPipe;
		this.shortPipe[1]=new int[shortPipe.length];
		for(int i=0;i<shortPipe.length;i++)
			this.shortPipe[1][i]=-1;
	}

	public int maximizer(int curNumOfPipe) {
		int l=longPipe.length, s=shortPipe[0].length;
		int maxNumOfPipe=curNumOfPipe;
		for(int i=0;i<s;i++) { 								//i번째 shortPipe를 잘라낼 수 있는지 하나씩 확인하려 함
			if(shortPipe[1][i]==-1) {						//i번째 shotrPipe가 처리되지 않은 파이프(-1)일 때만 자르는 과정 수행
				for(int j=0;j<l;j++) {						//longPipe중 shortPipe를 잘라낼 수 있는 j번째 longPipe를 찾음
					int compare=longPipe[j];				//j번째 longPipe에서 이미 잘라낸 양을 제해주기 위한 계산
					for(int k=0;k<s;k++) {
						if(shortPipe[1][k]==j)				//j번째 longPipe에서 제해 준 shortPipe를 골라 long에서 뺌
							compare-=shortPipe[0][k];
					}
					if(compare>=shortPipe[0][i]) {
						shortPipe[1][i]=j;
						int n=this.maximizer(curNumOfPipe+1);
						if(maxNumOfPipe<n)
							maxNumOfPipe=n;
						shortPipe[1][i]=-1;
					}
				}
			}
		}
		return maxNumOfPipe;
	}

	public static void main(String[] args) {
		int M=Integer.parseInt(args[0]);
		int[] longPipe=new int[M];
		for(int i=0;i<M;i++)
			longPipe[i]=Integer.parseInt(args[i+1]);
		int N=Integer.parseInt(args[M+1]);
		int[] shortPipe=new int[N];
		for(int i=0;i<N;i++)
			shortPipe[i]=Integer.parseInt(args[M+i+2]);

		long start=System.currentTimeMillis();
		Arrays.sort(longPipe);
		Arrays.sort(shortPipe);
		
		Pipe pipe=new Pipe(longPipe,shortPipe);
		System.out.println(pipe.maximizer(0));
		System.out.println((System.currentTimeMillis()-start)/1000.0);
	}
}