글 읽기 - 시간 초과가 나네요 ㅡㅡ

raisondet 8년 전 0

매초마다 모든 개미들의 위치와 방향을 확인하는 방법으로 코드를 짰는데요.

이중 loop로 되어 있어서 T와 N이 최대값일 경우, 시간 초과가 나네요.

그런데, 시간을 어떻게 줄여야 할지 모르겠습니다.

조언 부탁 드립니다.

#include "stdio.h"

typedef struct ant {
	int pos;
	char d;
}ANT;

ANT data[70005];
ANT copy[70005];
int L;
int T;
int N;

void print_d() {
	for (int i = 1; i <= N; i++) {
		printf("%c ", data[i].d);
	}
	printf("\n");
	for (int i = 1; i <= N; i++) {
		printf("%d ", data[i].pos);
	}
	printf("\n");
}

void change_d(int i) {
	if (data[i].d == 'L')
		data[i].d = 'D';
	else
		data[i].d = 'L';
}


void merge(int st, int ed) {
	int mid = (st + ed) / 2;
	int i = st;
	int j = mid + 1;
	int k = st;

	while (i <= mid && j <= ed) {
		if (data[i].pos <= data[j].pos) copy[k++] = data[i++];
		else copy[k++] = data[j++];
	}

	while (i <= mid) copy[k++] = data[i++];
	while (j <= ed) copy[k++] = data[j++];
	for (int i = st; i <= ed; i++) {
		data[i] = copy[i];
	}
}

void sort(int st, int ed) {
	if (st == ed)return;

	int mid = (st + ed) / 2;
	sort(st, mid);
	sort(mid + 1, ed);
	merge(st, ed);
}


void sort_() {
	ANT tmp;
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			if (data[i].pos > data[j].pos) {
				tmp = data[i];
				data[i] = data[j];
				data[j] = tmp;
			}
		}
	}
}

int main() {

	scanf("%d %d", &L, &T);
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d %c", &data[i].pos, &data[i].d);
	}

    int time = 1;
	while (time <= T) {
		for (int i = 1; i <= N; i++) {

			// 이동
			if (data[i].d == 'L') {
				data[i].pos--;
			}
			else
				data[i].pos++;

			// 방향 전환
			if (data[i].pos == 0) {
				change_d(i);
			} 
			else if (data[i].pos == L) {
				change_d(i);
			}
		}

		time++;
	}

	//sort_();
	sort(1, N);
	for (int i = 1; i <= N; i++) {
		printf("%d ", data[i].pos);
	}
	return 0;
}

mastojun 8년 전 0

(2 ≤ L ≤ 200,000, 1 ≤ N ≤ 70,000) 이기 때문에 O(L * N) 은 시간초과가 날 수 밖에 없습니다.

2마리가 서로 바라보고 움직일 때, 부딪히고 난다음에는 서로의 위치가 어떻게 되나요? 만약 얘네들이 초능력을 써서 부딪혀도 서로 뚫고 지나간다면 어떤 차이가 있을까요?

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

문제

문제

출처

ICPC

시간 초과가 나네요 ㅡㅡ

raisondet 8년 전 0

mastojun 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말