글 읽기 - 10158개미문제가 계속 시간초과가 나는데 도와주세요~ㅜ

topjlim 9년 전 0

도와주세요

1. 우선 처음에 2차원 배열로 해야되나? 생각했는데 40000 * 40000이라서 이건 아닌거 같애서 이 방법은 넘겼습니다.

2. 개미의 진행방향과 시간을 인자로 가지는 재귀함수를 호출해서 구하면 어떨까?

=> 구현했더니 예제에 대한 답이 나왔습니다! 오호

3. But 시간 초과가 났습니다. ㅠㅠ 재귀함수 호출을 무지막지하게 해야 되는 방법이라는 것을 깨달았습니다.

4. 개미가 한 바퀴를 돌고 또 도는 동작이 있다는 걸 발견했습니다. 이렇게 되면 200000000이런식의 수행횟수를 돌아야 하더라도

재귀 호출 횟수를 엄청 줄여 줄 수 있다고 생각했습니다.

그래서 재귀함수 호출을 하는 소스를 사용하면서 위의 사이클을 발견해서 그 부분의 계산량을 줄여주었습니다.

그래도 시간 초과 ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ

제가 만든 소스로 예제도 제대로 답이 나오고 제가 만든 몇 가지 테스트 케이스도 답이 나와서 답을 제대로 도출하지 않는 것은

아닌거 같고요. 근데 시간초과가 너무 심하네 요 ㅜㅜㅜ

도움 부탁드립니다.

#include <iostream>
using namespace std;

int garo, sero;
int result_x, result_y;
int result_hour;
int start_x, start_y;

void ant_movement(int x, int y, bool garostate, bool serostate, int movehour){
	// 조건에 제시한 시간과 현재 개미가 진행한 시간이 같다면 그 것이 답입니다!!
	if (movehour == result_hour){
		result_x = x;
		result_y = y;
		return;
	}
	int nextmovehour;
	int next_x, next_y;
	bool nextstate_x, nextstate_y;
	
	// 다음에 진행 할 개미의 방향을 증가감소 직선을 표현하듯이 표현해봤습니다.
	// 벽을 만나면 방향이 바뀐는 부분을 이렇게 표현했습니다. 
	if (x == garo || x == 0){
		nextstate_x = !garostate;
	}
	else{
		nextstate_x = garostate;
	}
	if (y == sero || y == 0){
		nextstate_y = !serostate;
	}
	else{
		nextstate_y = serostate;
	}
	// 진행 방향에 따라 다음의 좌표를 계산해주었구요
	if (nextstate_x){
		next_x = x + 1;
	}
	else{
		next_x = x - 1;
	}
	if (nextstate_y){
		next_y = y + 1;
	}
	else{
		next_y = y - 1;
	}
	// 이 부분이 개미가 진행하는 경로 중 반복되는 부분을 발견(한바퀴를 돌고 또 돈다는 것입니다)해서 그 부분의 연산을 
	// 줄여주었습니다. 
	if (movehour != 0 && x == start_x && y == start_y && nextstate_x && nextstate_y){
		nextmovehour = (result_hour / movehour) * movehour + 1;
	}
	else{
		nextmovehour = movehour + 1;
	}
	// 이렇게 재귀호출을 반복해서 답을 구해줬습니다. 
	ant_movement(next_x, next_y, nextstate_x, nextstate_y, nextmovehour);
}

int main(){
	cin >> garo >> sero;
	cin >> start_x >> start_y;
	cin >> result_hour;
	
	ant_movement(start_x, start_y, true, true, 0);
	
	cout << result_x << " " << result_y << endl;

	return 0;
}

portableangel 9년 전 2

한칸씩 진행하지 않고 벽에 부딪힐 때까지 한 번에 진행하는 방식으로 AC가 가능합니다.

근데 그 외의 방법으로 x좌표와 y좌표를 따로따로 계산하면 쉬운 규칙이 있어서 ㅋㅋㅋ

x만 보면 좌우로 왔다갔다 할뿐이고 y로 보면 위아래로 왔다갔다 할 뿐이니까요

그걸로 짧고 빠른 코드를 짤 수가 있어요

topjlim 9년 전 0

portableangel 님 감사합니다!

조언 해주신 방법으로 다시 풀어보겠습니다.!!!

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