[백준] 10654 Cow Jog - Data Structure / Java

graycode 2023. 6. 30. 19:46

• 문제 링크

10654번: Cow Jog

The cows are out exercising their hooves again! There are N cows jogging on an infinitely-long single-lane track (1 <= N <= 100,000). Each cow starts at a distinct position on the track, and some cows jog at different speeds. With only one lane in the tr

www.acmicpc.net

• 풀이 과정

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        long t = Long.parseLong(st.nextToken());

        Stack<Long> stk = new Stack<>();

        while (n-- > 0) {
            st = new StringTokenizer(br.readLine());
            long reach = Long.parseLong(st.nextToken()) + Long.parseLong(st.nextToken()) * t;

            while (!stk.empty() && stk.peek() >= reach) stk.pop();

            stk.push(reach);
        }

        bw.write(String.valueOf(stk.size()));
        bw.flush();
    }

}