1092_배

사용 알고리즘: 그리디

사용 언어: java

 

package week15;

import java.io.*;
import java.util.*;

public class Main_bj_1092_배 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); //배 개수
		int[] ships = new int[n];
		for (int i = 0; i < ships.length; i++) {
			ships[i] = sc.nextInt();
		}
		Arrays.sort(ships);
		
		ArrayList<Integer>[] cargoes = new ArrayList[n+1]; //배보다 작은 애들 
		for(int i=0; i<n+1; i++) {
			cargoes[i] = new ArrayList<>();
		}
		
		int m = sc.nextInt(); //화물 개수

		for(int i = 0; i < m; i++) {
			int cargo = sc.nextInt();
			boolean canLift = false;
			for(int j=0; j<n; j++) {
				if(ships[j] >= cargo) {
					cargoes[j].add(cargo);
					canLift = true;
					break;
				}
			}
			if(!canLift) cargoes[n].add(cargo);
		}
//
		
		int answer = 0;
		if(cargoes[n].size() > 0)
			System.out.println(-1);
		else {
			int cnt = 0;
			while(true) {
				if(cnt == m) break;
				answer ++;
				
				boolean used[] = new boolean[n];
				for(int i=n-1; i>=0; i--) {
					if(cargoes[i].size() > 0) {
						cargoes[i].remove(0);
						cnt++;
						used[i] = true;
					}
					else {
						for(int j=i-1; j>=0; j--) {
							if(cargoes[j].size() > 0) {
								cargoes[j].remove(0);
								cnt++;
								used[i]= true;
								break;
							}
						}
					}
				}
			}
			
			System.out.println(answer);
		}
		
	}

}

 

 

그리디 문제라고 한다.

다른 블로그 참고해보니까, 메모리를 좀 더 효율적으로 쓰는 방법이 따로 있는 거 같다.

 

나는 박스 개수에 맞게 ArrayList를 만들었고, 해당 화물을 실을 수 있는 배 중 최소값을 찾아, 그 배에 줄 세워놨다.

만약 본인(배)에게 더 이상 들고 갈 화물이 없다면, 자기보다 작은 배에 줄 서 있는 화물 중 가장 큰 것을 자신이 들고 가면서 최적화하려고 했다.