백준 13335 트럭 (JAVA 자바)

문제 출처: https://www.acmicpc.net/problem/13335

13335번: 트럭

 

문제 유형: 구현/시뮬레이션

 

구현 문제다 보니 다양한 풀이 방법이 있겠지만 나는 시간대별로 계산하는 방법으로 풀었다.

길이가 W인 다리라면 그 얘기는 즉 다리에 한번에 올라갈 수 있는 트럭의 수도 W 대라는 말이다. 

따라서 현재 다리 위에 올라가 있는 트럭의 수를 cntT로 하여 

현재 트럭의 수가 W보다 작고 현재 다리 위에 올라가 있는 트럭의 무게(curW)와 다음 트럭 (idx)의 무게 합이 L보다 작다면 다리 위에 트럭을 또 올릴 수 있으니까 트럭을 올려주고 curW도 올려주고 트럭 한 대를 올렸으니까 cntT도 올리고 한다. 크다면 올리지 않는다. 아무튼 한 턴을 돌 때마다 트럭이 다리를 건너느라 걸리는 시간인 W가 1씩 감소하게 되니까 onBridge 배열의 원소들을 1씩 감소시켜준다.

 

글로 풀어서 설명하면 장황한데 차근차근 생각해보면 나름 나쁘지 않다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N, W, L;
	static int truck[], onBridge[];
	static int cntT, curW, idx, former, last;
	static int res;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		
		
		truck = new int [N];
		onBridge = new int [N];
		Arrays.fill(onBridge, -1);
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			truck[i] = Integer.parseInt(st.nextToken());
		}
		while(true) {
			if(idx == N && check()) {
				res++;
				break;
			}
			
			for (int i = former; i < idx; i++) {
				if(onBridge[i] == 0) {
					cntT--;
					curW -= truck[i];
					former++;
				}
				
			}
			
			// onTruck size가 W와 같으면 
			if(cntT < W) {
				if(idx < N && curW + truck[idx] <= L) {
					curW += truck[idx];
					cntT++;
					onBridge[idx] = W;
					idx++;
				}
				// 작으면 
			}

			res++;
			for (int i = former; i < idx; i++) {
				// 안에 있는 트럭들 시간 -1 해주고
				if(onBridge[i] > 0) {
					onBridge[i]--;
				}
			}
		}
		System.out.println(res);
			
	}
	
	static boolean check() {
		for (int i = 0; i < N; i++) {
			if(onBridge[i] != 0)
				return false;
		}
		return true;
	}
}