[Baekjoon] 10654_Cow Jog

문제(출처: https://www.acmicpc.net/problem/10654)

---

< Cow Jog >

 

문제 풀이 

 

Stack을 사용하여 초기 위치가 큰 소들부터 T 시간 움직여 뒤에서 출발한 소가 추월하지 못하게 한다.

만약 3분 동안 달리고 초기 위치와 속도가 다음과 같다면
6 1

4 2

6에 있던 소는 9, 3에 있던 소는 10이 돼야 하는데 추월할 수 없으므로 stack에는 9만 넣는다.

 

결론 : stack에 초기 위치가 멀리 있던 소부터 움직여 움직인 위치를 저장한 뒤, 다른 소들의 움직인 위치가 앞에 소보다 작을 때만 stack에 저장한다.

 

my solution (Java)

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

public class _10654_ { // Cow Jog

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

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

		Stack<Long[]> stack = new Stack<>();

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			stack.add(new Long[] { Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()) });
		}

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

		while (!stack.isEmpty()) {
			Long[] info = stack.pop();
			long d = info[0] + info[1] * t;
			if (result.isEmpty()) {
				result.add(d);
			} else {
				if (result.peek() > d) {
					result.add(d);
				}
			}
		}
		System.out.println(result.size());
	}
}

변수)
n, t : 소 마릿수, 달린 시간
stack : 소의 초기 위치, 속도 정보를 저장한 Stack
result : 소 그룹을 구하기 위한 Stack
d : 이동한 위치 

 

소 마릿수와 달린 시간을 입력받는다. n만큼 소의 정보를 입력받아 소의 초기 위치 기준으로 오름차순으로 입력되므로 stack에 저장한다. stack이 빌 때까지 다음 과정을 반복한다.

1) stack pop

2) 초기위치 + 속도 * 달린 시간 구하기

3) result가 비어있다면 첫 번째 소 이므로 result에 저장

4) result가 비어있지 않다면 result의 peek 값보다 작을 때만 result에 저장

 

최종 result의 size를 출력한다. 

---

---