[백준 1680] 쓰레기 수거 - JAVA

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

 

구현 문제

 

조건이 낚시 수준이라 다음 케이스가 이해 안간다면 글을 보고 시작하는 것이 좋다.

https://www.acmicpc.net/board/view/119329

 

1

2 2

1 1

2 2

ans: 8

wa: 6

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int T = Integer.parseInt(br.readLine());

    while (T-- > 0) {
      st = new StringTokenizer(br.readLine());
      int W = Integer.parseInt(st.nextToken());
      int N = Integer.parseInt(st.nextToken());

      int nd = 0;
      int nw = 0;

      int[] d = new int[N];
      int[] w = new int[N];

      for (int i = 0; i < N; i++) {
        st = new StringTokenizer(br.readLine());
        d[i] = Integer.parseInt(st.nextToken());
        w[i] = Integer.parseInt(st.nextToken());
      }

      int i = 0;
      int at = 0;
      while (i < N) {

        while (i < N && nw + w[i] <= W) {
          nw += w[i];
          nd += d[i] - at;
          at = d[i];
          i++;
        }

        // 1. 쓰레기의 양이 용량에 도달했을 때.
        if (nw == W) {
          nw = 0;
          nd += at;
          at = 0;
        } else if (i < N) {

          // 일단 가야함
          nw += w[i];
          nd += d[i] - at;
          at = d[i];

          // 2. 그 지점의 쓰레기를 실었을 때 쓰레기차의 용량을 넘게 될 때
          if (nw + w[i] > W) {
            nw = 0;
            nd += at;
            at = 0;
          }
        }
      }

      // 3. 더 이상 쓰레기를 실을 지점이 없을 때.
      System.out.println(nd + at);
    }
  }
}