글 읽기 - 같은 로직 같은데 하나가 시간초과 납니다

whdgurclzls 3년 전 0

안녕하세요! 시간초과가 났길래 이곳저곳 코드를 바꿔가며 어느부분에서 시간초과가 나는지 찾아보았는데요

29~ 38 line을 수정하여 정답은 나왔습니다. (이곳이 원인이라고 찾았지만, 대체 왜 차이가 나는지를 모르겠습니다.)

정답 코드(댓글에 첨부하겠습니다)는 nx, ny를 기준으로 움직여준거고 시간초과 나는 코드는 x, y를 기준으로 움직여줬습니다. 제 머리로는 둘 다 같은 시간에 돌아갈거라고 기대 되는데 대체 어느 부분을 놓치고 있는걸까요?

cnt 전역변수 설정해서 while 반복문 돌아갈때마다 증가시켜서 혹시나 반복문 실행에 차이가 있나도 살펴보았는데 두 코드 똑같은 값이 나옵니다. 또한, 이동을 마친 후(while문이 종료 될 때마다) x, y의 좌표 값들도 모두 출력해보았는데 두 코드의 x, y 값이 모두 같게나옵니다. 차이가 나는 부분을 도저히 못찾겠는데 아래의 코드가 시간초과가 난 원인은 무엇일까요..?

시간내어 읽어주셔서 감사하고, 좋은하루 되셨으면 합니다!

#include<cstdio>
#include<vector>
#include<tuple>			
#include<cstring>
using namespace std;
typedef tuple<int, int, int> T;
typedef pair<int, int> P;
const int SIZE = 101;
int n, m, k;
T a[SIZE][SIZE], visit[SIZE][SIZE];
int dd[4][2] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
int searchD(int d){
	if (d == 0) return 1;
	if (d == 1) return 0;
	if (d == 2) return 3;
	if (d == 3) return 2;
}
void move(){
	vector<P> v;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++){
			int speed, d, size;
			tie(speed, d, size) = a[i][j];
			if (size != -1){
				a[i][j] = make_tuple(-1, -1, -1);
				int dx = dd[d][0], dy = dd[d][1];
				int nx = i, ny = j, time = speed;
				int x = i, y = j;
				while (time--){
					nx = x + dx, ny = y + dy;
					if (nx<0 || ny<0 || nx>n - 1 || ny>m - 1){
						x -= dx, y -= dy;
						d = searchD(d);
						dx = dd[d][0], dy = dd[d][1];
					}
					else
						x = nx, y = ny;
				}
				int vspeed, vd, vsize;
				tie(vspeed, vd, vsize) = visit[x][y];
				if (vsize != -1){
					if (vsize < size)
						visit[x][y] = make_tuple(speed, d, size);
				}
				else{
					visit[x][y] = make_tuple(speed, d, size);
					v.push_back({ x, y });
				}
			}
		}
	for (auto x : v){
		int i = x.first, j = x.second;
		a[i][j] = visit[i][j];
	}
}
int main(){
	scanf("%d %d %d", &n, &m, &k);
	memset(a, -1, sizeof(a));
	while (k--){
		int r, c, speed, d, size;
		scanf("%d %d %d %d %d", &r, &c, &speed, &d, &size);
		a[r - 1][c - 1] = make_tuple(speed, d - 1, size);
	}
	int res = 0;
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			int speed, d, size;
			tie(speed, d, size) = a[j][i];
			if (size != -1){
				res += size;
				a[j][i] = make_tuple(-1, -1, -1);
				break;
			}
		}
		memset(visit, -1, sizeof(visit));
		move();
	}
	printf("%d\n", res);
	return 0;
}

whdgurclzls 3년 전 0

수정한 코드 입니다.(28~35 line)

#include<cstdio>
#include<vector>
#include<tuple>			
#include<cstring>
using namespace std;
typedef tuple<int, int, int> T;
typedef pair<int, int> P;
const int SIZE = 101;
int n, m, k;
T a[SIZE][SIZE], visit[SIZE][SIZE];
int dd[4][2] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
int searchD(int d){
	if (d == 0) return 1;
	if (d == 1) return 0;
	if (d == 2) return 3;
	if (d == 3) return 2;
}
void move(){
	vector<P> v;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++){
			int speed, d, size;
			tie(speed, d, size) = a[i][j];
			if (size != -1){
				a[i][j] = make_tuple(-1, -1, -1);
				int dx = dd[d][0], dy = dd[d][1];
				int nx = i, ny = j, time = speed;
				while (time--){
					nx += dx, ny += dy;
					if (nx<0 || ny<0 || nx>n - 1 || ny>m - 1){
						nx = nx - 2 * dx, ny = ny - 2 * dy;
						d = searchD(d);
						dx = dd[d][0], dy = dd[d][1];
					}
				}
				int x = nx, y = ny;
				int vspeed, vd, vsize;
				tie(vspeed, vd, vsize) = visit[x][y];
				if (vsize != -1){
					if (vsize < size)
						visit[x][y] = make_tuple(speed, d, size);
				}
				else{
					visit[x][y] = make_tuple(speed, d, size);
					v.push_back({ x, y });
				}
			}
		}
	for (auto x : v){
		int i = x.first, j = x.second;
		a[i][j] = visit[i][j];
	}
}
int main(){
	scanf("%d %d %d", &n, &m, &k);
	memset(a, -1, sizeof(a));
	while (k--){
		int r, c, speed, d, size;
		scanf("%d %d %d %d %d", &r, &c, &speed, &d, &size);
		a[r - 1][c - 1] = make_tuple(speed, d - 1, size);
	}
	int res = 0;
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			int speed, d, size;
			tie(speed, d, size) = a[j][i];
			if (size != -1){
				res += size;
				a[j][i] = make_tuple(-1, -1, -1);
				break;
			}
		}
		memset(visit, -1, sizeof(visit));
		move();
	}
	printf("%d\n", res);
	return 0;
}

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

문제

문제

출처

ICPC

같은 로직 같은데 하나가 시간초과 납니다

whdgurclzls 3년 전 0

whdgurclzls 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말