[BOJ] 13335. 트럭(시뮬레이션).java

#. Problem

https://www.acmicpc.net/problem/13335

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

시간복잡도가 까다롭지 않아서 

Naive하게 해결할 수 있는 문제다.

O(n*w) = O(1000 * 100)

1. 다리 위의 트럭이 이동

2. 다리를 건넌 트럭이 있다면,

다리의 하중을 트럭의 무게만큼 줄여주자.

3. 다리에 대기 중인 트럭이 올라올 수 있다면,

다리에 트럭을 올려주고, 다리의 하중을 올려주자.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ13335 {       static int n, w, L, trucks[], bridge[];          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()); // 다리의 최대하중                  bridge = new int[w];         trucks = new int[n];         st = new StringTokenizer(br.readLine());         for (int i = 0; i < n; i++) {             trucks[i] = Integer.parseInt(st.nextToken());         }           System.out.println(process());     }       private static int process() {                  int time = 0, weight = 0, idx = 0;         // 모든 트럭이 다리를 건널 때까지         while(idx < n) {             // 다리 위의 트럭이 이동             int reach = bridge[0];             for (int i = 1; i < w; i++) {                 bridge[i - 1] = bridge[i];              }             bridge[w - 1] = 0;                          // 다리를 건넌 트럭이 있다면             if(reach != 0 ) {                 weight -= reach;             }             // 다리에 대기중인 트럭이 올라올 수 있다면             if(idx < n && weight + trucks[idx] <= L) {                 bridge[w - 1] = trucks[idx];                 weight += trucks[idx];                 idx++;             }                          time++;         }                  // 마지막에 다리에 오른 트럭이 다리를 건너는 시간을 추가         return time + w;     }      } Colored by Color Scripter

cs