백준 13335 - 트럭(java)

www.acmicpc.net/problem/13335

13335번: 트럭

1. 유형

구현

 

2. 자료구조

ArrayList, 큐

 

3. 기능구현

트럭을 한칸 씩 앞으로

트럭중 다리 벗어난거 제외

다음 트럭이 다리에 올라 올 수 있다면 올려놓기

 

4. 풀이

Pair의 필드값으로 트럭의 무게, 다리에서 흘러간 시간을 설정한다.

반복문은 주어진 트럭이 전부 다리에 올라온 시점에서 반복문 탈출

그리고 3번의 기능들을 순서대로 반복문 안에서 구현해 준다.

 

여기서 주의 할점은 다리에 올라온 시점에서 반복문을 멈추기 때문에

마지막에 list.size()>0 일때, 즉, 다리에 아직 트럭이 있다는 뜻이다.

트럭이 다리에서 전부 지나가야 하니깐 +다리길이 만큼 더해줘야 한다.

 

끝..

 

코드.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, W, L;

	static class Pair {
		int val, time;

		public Pair(int val, int time) {
			// TODO Auto-generated constructor stub
			this.val = val;
			this.time = time;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		W = Integer.valueOf(st.nextToken());
		L = Integer.valueOf(st.nextToken());
		st = new StringTokenizer(in.readLine());
		Queue<Integer> queue = new LinkedList<Integer>();
		for (int i = 0; i < N; i++) {
			queue.add(Integer.valueOf(st.nextToken()));
		}
		ArrayList<Pair> list = new ArrayList<>();
		int total = 0;
		int idx = 0;
		while (!queue.isEmpty()) {
			for (Pair p : list) {
				p.time++;
			}
			if (list.size() > 0 && list.get(0).time > W) {
				total -= list.get(0).val;
				list.remove(0);
				
			}
			if (total + queue.peek() <= L && list.size() < W) {
				int tmp = queue.poll();
				total += tmp;
				list.add(new Pair(tmp, 1));
			}
			idx++;
		}
		if(list.size()>0) {
			idx+=W;
		}
		System.out.println(idx);
	}
}

5. 느낀점

맨처음 어떤 자료구조를 써야할지 많이 고민했다.

하지만 항상 그렇듯 ArrayList 아니면 큐로 해결할 수 있었다.

다양한 문제를 풀어보며 빠른 접근 방식을 익혀야겠다.