글 읽기 - 후... 시뮬레이션을 하지 않고 그냥 푸는 방법을 도저히 모르겠습니다 ㅠㅠㅠ

kimjh9434 5년 전 0

나름대로 계속 확인해보고 있지만 답이 계속 안나오고 있내요...

일단 시뮬레이션처럼 일일히 시간의 경과를 0.5초씩 돌려서, 튕기는걸 모두 고려하면서 진행해본 결과

물론 정확하게 답은 나오는데, 7% 대에서 시간초과가 나오는걸로 봐서 이 방향은 아닌것 같더군요.

[느낌상, N이 최대 100000, L이 최대 5000000 이다보니, 0.5mm 진행 마다 N(= 100000 )번 반복하면서 가면

어마어마하게 오래 진행되서 그런것 같다는 생각도 듭니다]

지금까지 질문 게시판을 통해서 어떻게든 해결해 왔는데, 이번건 질문이 너무 적어서 어떻게 해야할지 감이 잘 안오는 상황입니다.

일단 다른 질문들을 확인해보면

중요하다고 하시는 점이 "번호간의 순서는 절대 바뀌지 않는다.", '"개미의 순서가 변하지 않는다라는 것만 알면 쉬운 문제입니다." 라고 하시는데, 그걸 알아도 감이 라고 하는데, 이는 당연한 얘기지만, 이를 어떻게 적용해야 할지 도저히 감이 안오더군요.

물론 이를 통해서 해당 개미가 왼쪽으로 떨어질지, 오른쪽으로 떨어질지는 구할수가 있긴 있습니다.

오른쪽 으로 진행하는 개미의 수 : 왼쪽으로 진행하는 개미의 수 = M : N이라고 하면,

최종적으로는, 막대의 왼쪽에서 떨어지는 개미의 수 : 막대의 오른쪽에서 떨어지는 개미의 수 = N : M이 된다는 겁니다.

가령 → ← ← → ← ← 등 으로 2 : 4 라면 최종적으로는 ← ← ← ← → → 로 4:2로 떨어진다는 의미입니다.

하지만, 결국 떨어지는 순서를 명확하게 하기 위해서는, 이 개미가 어디로 떨어지냐도 중요하지만, '언제' 떨어지냐가 가장 중요한데

이를 시뮬레이션 처럼 돌려보지 않고서도, 한번에 구할수 있는 방법이 있는지요???

가령 첫번째 입력 예제를 놓고 보겠습니다.

T = 0 일 때,

5 4 →

8 5 →

19 -1 ←

22 -3 ←

24 -2 ←

25 6 →
인 상황으로, 중간에 어떻게 충돌할지는 모르겠지만 결론적으로 ← ←← →→ → 으로 간다는 것을 알 수가 있습니다.

그러면 적어도 현재 위치와, 현재 방향, 그리고 최종적으로 가게 되는 방향을 통해서 대략적인 유추는 가능합니다.

5 4     ← 5 + ???
8 5 ← 8 + ???
19 -1   ← 19 + ???
22 -3   → 8 + ???
24 -2   → 6 + ???
25 6 → 5

적어도 여기서는 6번 개미가 제일 먼저 나온다는 것 말고는 모르겠군요...

결론적으로는

5 4 ← 5 + 14 = 19초 - 2등
8 5   ← 8 + 14 = 22초 - 4등
19 -1   ← 19 + 5 = 24초 - 5등
22 -3   → 8 + 17 = 25초 - 6등
24 -2   → 6 + 16 = 22초 -3등
25 6 → 5초 - 1등 이 되어야 하는데, 중간 과정을 도저히 유추해 내지 못하겠습니다...

가령 길이가 10인 막대에 개미 2마리 A(위치 2, →) , B(위치 6, ←)가 각각 있다고 하면,

A가 떨어질때까지의 시간은, (6-2)/2 + 4 = 6 이고,

B가 떨어질때까지의 시간은, (6-2)/2 + (10-4) = 8입니다. [A와 B의 충돌지점은 중간지점인 4]

여기서, C(위치 8, ←) 이었던 개미가 있었다고 가정하면,

A가 떨어질때까지의 시간은, (6-2)/2 + 4 = 6 으로 똑같고,

B가 떨어질때까지의 시간은, (6-2)/2 + (6-4)/2 + (5) = 8이며,

C가 떨어질때까지의 시간은, (6-2)/2 + (6-4)/2 + (5) = 8입니다. [B와 C의 충돌지점은 그 당시 4, 6의 중간지점인 5]

C의 초기 위치가 7이었으면, B는 7초가 걸리고, C는 8초가 되며, [B와 C의 충돌지점은 그 당시 4, 7의 중간지점인 5.5]

C의 초기 위치가 9 이었으면, B는 9초가 걸리고, C는 8초가 됩니다. [B와 C의 충돌지점은 그 당시 4, 5의 중간지점인 4.5]

이는 결국 실제 충돌을 어디에서 했고, 그 당시 개미들의 위치가 중요하며, 이를 추적해 나가야 할것 같은데...

그렇게 진행하면 시간초과가 나고...

도대체, 직접 충돌을 확인하지도 않고서도 이 문제를 푸는 방법이 있다면, 힌트라도 주시면 감사하겠습니다!!!

PS. 혹시 몰라서 일단 제가 했던 코드는 올려보았습니다.

import java.util.Scanner;

public class Main {
	// static double time;
	public static void main(String[] args) {
		// Q10 3163 떨어지는 개미

		// 2018-09-01-토 ~ 2018-09-02-일

		// 3차 도전!
		// 빡쳐서 걍 연결리스트를 써봐야겠다.
		// 으아이니!!! 이번에도 7%에서 시간초과가 나온다.

		Scanner sc = new Scanner(System.in);

		int T;
		int N;
		AntLinkedList list;
		int i, j;
		int answer;

		list = new AntLinkedList();
		T = sc.nextInt();
		for (i = 0; i < T; i++) {
			// 기본값 세팅
			N = sc.nextInt();
			list.L = sc.nextInt();
			list.K = sc.nextInt();
			answer = 0;
			// time = 0;

			// 리스트를 만든다.
			for (j = 0; j < N; j++) {
				list.add_rear(sc.nextInt(), sc.nextInt());
			}

			//list.print();

			// K번째 개미가 떨어지기 전까지 반복한다.
			while (true) {
				// 0.5초 경과
				list.half_Second_Later();
				answer = list.check();
				//list.print();

				if (answer != 0)
					break;
			}
			System.out.println(answer);

			list.reset();
		}

		sc.close();
	}
}

// 개미 노드 [이중 연결리스트]
class Node {
	Node prev;
	Node next;

	double pos;
	int id;
	double dir; // direction

	Node(int pos, int id) {
		this.prev = null;
		this.next = null;
		this.pos = pos;
		this.id = id;
		this.dir = (id > 0) ? 0.5 : -0.5;
	}
}

class AntLinkedList {
	Node front;
	Node tail;
	int length;
	int L;
	int K;
	int order;

	AntLinkedList() {
		front = null;
		tail = null;
		length = 0;
		L = 0;
		K = 0;
		order = 0;
	}

	// 디버깅용 메소드
	public void print() {
		Node current = front;
		while (current != null) {
			System.out.print(current.id + "(" + current.pos + ") ");
			current = current.next;
		}
		System.out.println();
		System.out.println();
	}

	public void Change(Node a, Node b) {
		// 주변 링크 수정
		if (a != front && b != tail) {
			a.prev.next = b;
			b.next.prev = a;
		} else {
			if (a == front) {
				front = b;
				b.next.prev = a;
			} else if (b == tail) {
				a.prev.next = b;
				tail = a;
			}
		}
		// 본인들 직접 수정
		b.prev = a.prev;
		a.next = b.next;
		a.prev = b;
		b.next = a;
	}
    
    // 0.5초 후를 진행하는 메소드
	public void half_Second_Later() {
		Node current;
		int tmp;

		current = front;
		while (current != null) {
			current.pos += current.dir;
			current = current.next;
		}

		current = front;
		while (current != null) {
			if (current.next != null && current.pos >= current.next.pos) {
				// id 변경
				tmp = current.id;
				current.id = current.next.id;
				current.next.id = tmp;

				// 노드의 위치 변경
				Change(current, current.next);
			}
			current = current.next;
		}
	}

    // 맨 끝에 도달한 개미가 있는지 검사하는 메소드
	public int check() {
		if ((front.pos == 0) && (tail.pos == L)) {
			if (front.id < tail.id) {
				if (++order == K) {
					return front.id;
				}
				delete_front();

				if (++order == K) {
					return tail.id;
				}
				delete_tail();
			} else {
				if (++order == K) {
					return tail.id;
				}
				delete_tail();

				if (++order == K) {
					return front.id;
				}
				delete_front();
			}
		} else {
			if (front.pos == 0) {
				if (++order == K) {
					return front.id;
				}
				delete_front();
			}
			if (tail.pos == L) {
				if (++order == K) {
					return tail.id;
				}
				delete_tail();
			}
		}
		return 0;
	}

	public boolean isEmpty() {
		return (length == 0);
	}

	public void add_rear(int pos, int id) {
		Node n = new Node(pos, id);
		if (!isEmpty()) {
			tail.next = n;
			n.prev = tail;
			tail = n;
		} else {
			front = n;
			tail = n;
		}
		length++;
	}

	public void delete_front() {
		if (!isEmpty()) {
			if (length != 1) {
				front.next.prev = null;
				front = front.next;
			} else {
				front = null;
				tail = null;
			}
			length--;
		}
	}

	public void delete_tail() {
		if (!isEmpty()) {
			if (length != 1) {
				tail.prev.next = null;
				tail = tail.prev;
			} else {
				front = null;
				tail = null;
			}
			length--;
		}
	}

	public void reset() {
		front = null;
		tail = null;
		length = 0;
		L = 0;
		K = 0;
		order = 0;
	}
}

djm03178 5년 전 4

이 문제는 방법을 알면 나머지는 정말 코드로 그대로 구현하는 것 뿐입니다. 힌트를 좀 더 강화해서 드리겠습니다.

충돌을 충돌이라고 생각하지 말고, 항상 그대로 뚫고 지나간다고 생각해 보세요. 그러면 어떤 시점에서 어떤 방향으로 시작하는 개미가 언제 떨어질지는 알 수 있겠죠?

그리고 이번엔 다시 충돌 개념을 생각해서, 왼쪽 방향으로 시작하는 개미가 N마리, 오른쪽 방향으로 시작하는 개미가 M마리이면, 처음의 N+M마리 중 왼쪽에 있던 N마리가 왼쪽으로 떨어지고, 오른쪽에 있던 M마리가 오른쪽으로 떨어진다는 것도 이해 되시나요?

그러면 충돌이 없는 상태에서 "왼쪽 방향으로" 시작한 개미들이 떨어지는 시간을, 충돌이 있는 상태에서 "왼쪽에서" 시작한 개미들에 차례대로 대응만 시켜주면 됩니다.

kimjh9434 5년 전 0

그렇군요!!!

댓글을 달아주신걸 보고서 곰곰히 생각을 해본 결과,

'충돌을 충돌이라고 생각하지 말고, 항상 그대로 뚫고 지나간다고 생각해 보세요. 그러면 어떤 시점에서 어떤 방향으로 시작하는 개미가 언제 떨어질지는 알 수 있겠죠?' 라는 힌트가 가장 결정적이었던것 같습니다.

전에는 ' 개미의 인덱스 순서는 절대 바뀌지 않습니다.'를 충돌시 id값을 바꾸는 식으로 시도해 보았지만, 그래도 충돌이 언제 일어나는지는 알아야 하는 용도로 사용했었는데, 아예 다 무시하고 끝까지 간다고 보니까 뭔가 보이더군요. [처음 개미의 출발 방향, 최종적으로 마무리되는 개미의 방향, 처음 개미가 끝까지 갈때의 이동거리, 결국 해당 개미가 끝에 도달할때까지의 이동거리를 확인하다가 깨달았습니다]

실질적으로 각 개미의 이동해야 할 거리(도착 시간까지의 시간)을 쭉 얻고, 시간순으로 정렬한 다음에, K번째 개미의 id값을 출력하니까 맞았습니다.

[처음 시도는 ArrayList를 썼는데, add 연산이 오래걸렸는지 시간초과가 떠서, 죄다 배열로 바꾸니까 통과됬습니다]

이거를 가지고 2일 이상 고민했었는데... 감사합니다!

ha_ram 5년 전 0

저도 도움이 많이 됐어요~ 뚫고 지나간다고 생각하라니... ㄷㄷㄷㄷ 신선한 충격을 받았습니다.

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

후... 시뮬레이션을 하지 않고 그냥 푸는 방법을 도저히 모르겠습니다 ㅠㅠㅠ

kimjh9434 5년 전 0

djm03178 5년 전 4

kimjh9434 5년 전 0

ha_ram 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말