[Baekjoon] 10657_Cow Jog

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

---

< Cow Jog >

 

문제 풀이 

 

두 가지 방식으로 문제를 해결할 수 있다.

1) 소들을 속도에 맞게 이동시키면서 그룹 만들기

2) 속도만 보고 그룹 만들기 -> 자신보다 뒤에 있는 소가 속도가 빠르다면 결국 같은 그룹으로 묶이게 된다.

 

my solution (Java)

1)

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

public class _10657_ { // Cow Jog

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

		int N = Integer.parseInt(bf.readLine());

		ArrayList<Long[]> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());

			list.add(new Long[] { Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()) });
		}

		Stack<Long[]> stack = new Stack<>();
		boolean flag = false;
		while (true) {
			for (int j = list.size() - 1; j >= 0; j--) {
				if (!stack.isEmpty() && stack.peek()[1] < list.get(j)[1]) {
					flag = true;
				}
				if (stack.isEmpty() || list.get(j)[0] + list.get(j)[1] < stack.peek()[0]) {
					stack.add(new Long[] { list.get(j)[0] + list.get(j)[1], list.get(j)[1] });
				}
			}
			list.clear();
			while (!stack.isEmpty()) {
				list.add(stack.pop());
			}
			if (!flag) {
				System.out.println(list.size());
				break;
			}
			flag = false;
		}
	}
}

변수)
N : 소 마릿수
list : 입력값
stack : Stack <Long []> 
flag : 뒤에 있는 소가 속도가 빠른 경우

 

소의 수를 입력받는다. 소의 수만큼 현재 위치와 속도를 입력받아 ArrayList에 저장한다. 뒤에 있는 소가 앞에 있는 소보다 속도가 빠른 경우가 없을 때까지 다음 과정을 반복한다.

 

1) Stack에 현재 위치가 큰 소부터 속도에 맞게 이동하면서 저장한다. 이때, stack에 있는 소보다 멀리 가지 못하므로 stack에 있는 소보다 이동한 위치가 작을 경우에만 저장한다. 속도를 확인하며 stack에 있는 값보다 속도가 빠른 경우 flag를 true로 저장한다.

2) stack의 값을 ArrayList에 저장한다.

3) 뒤에 있는 소가 앞에 있는 소보다 속도가 빠른 경우가 없다면 그룹이 합쳐질 일이 없으므로 ArrayList의 크기를 출력하고 종료한다.

 

2)

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

public class _10657_ { // Cow Jog

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

		int N = Integer.parseInt(bf.readLine());

		ArrayList<int[]> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());

			list.add(new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) });
		}

		Stack<Integer> stack = new Stack<>();
		for (int i = N - 1; i >= 0; i--) {
			if (stack.isEmpty() || stack.peek() >= list.get(i)[1]) {
				stack.add(list.get(i)[1]);
			}
		}
		System.out.println(stack.size());
	}
}

변수)
N : 소 마릿수
list : 입력값
stack : Stack <Integer> 

 

소의 수를 입력받는다. N만큼 현재 위치와 속도를 입력받아 ArrayList에 저장한다. Stack에 현재 위치가 먼 소의 순으로 속도를 저장한다. 이때, stack에 있는 값의 속도보다 작거나 같을 때만 저장한다.

 

최종 stack의 크기를 출력한다.

---

---