알고리즘96 :: 거북이 문방구집

내용 : 대부호 거북이가 있었다. 거북이는 여러 문방구를 가지고 있는데 문방구는 한 사람씩밖에 못들어간다. 동물 친구들은 거북이 문방구를 이용하고자 한다. 각 동물 친구들이 이용할 수 있는 시간대와 들어가서 물건을 구매하는데 걸리는 시간이 존재한다. 만약, 토끼가 2초에 들어가서 문방구를 이용하는데 총 5초가 걸리는데 다음 다람쥐가 4초에서 문방구를 들어가려고 했다면 3초를 더 기다려야한다. 

문방구의 수 : N

동물 친구들 각각 문방구에 들어가는 시간 및 문방구를 이용하는데 걸리는 시간 : x,y

 

ㅡ. Step1

문방구의 개수만큼 배열을 생성한 후에 가장 이용시간이 적게 남은 문방구를 갱신해준다. 

 

ㅡ. Step2

이용시간이 적게 남아있는 문방구가 존재하는 상황에서 다음 문방구를 이용해야할 동물 친구와 시간을 비교해 동물 친구의 시간이 더 크거나 같다면 동물 친구가 문방구를 이용할 수 있다는 의미이다. 문방구 이용시간을 업데이트 한다. 

반대로 동물 친구의 시간이 더 작다면 이미 기다려야 할 시간을 오버한것이므로 두 값의 차이를 answer로 갱신하고 현재 동물 친구가 문방구를 이용하고 있는 시간이 되므로 현재 동물 친구의 문방구 이용시간을 합친다.

 

public class 거북이_문방구집 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int N=2;
		int answer = 0;
		int[] munbangu = new int[N];
		int min_munbangu = 0;
		int[][] total = {
				{2,3},
				{5,4},
				{6,3},
				{7,4}
		};
		
		for(int i=0; i<total.length; i++) {
			for(int j=0; j<munbangu.length; j++) {
				if(munbangu[j]<munbangu[min_munbangu])
					min_munbangu = j;
			}//end of for loop
			
			if(total[i][0]<munbangu[min_munbangu]) {
				answer += (munbangu[min_munbangu]-total[i][0]);
				munbangu[min_munbangu] += total[i][1];
			}else {
				munbangu[min_munbangu] = total[i][0] + total[i][1];
			}
		}
		System.out.println(answer);
	}

}