22. [백준 17143번 / C++] 낚시왕

https://www.acmicpc.net/problem/17143

17143번: 낚시왕

 

구현은 정말 빨리 했는데... 14%에서 계속 시간초과가 난 문제다.

 

 

도대체 시간 초과가 어디서 나는걸까? 일단 코드를 보자.

 

#include<bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, k, r, c, s, d, z, a[104][104], b[104][104], cnt, ret;
vector<tuple<int, int, int>> v; // 속도, 방향, 크기.

void catchFish(int cnt){
	for(int i = 1; i <= n; i++){
		if(a[i][cnt] != 0){
			ret += get<2> (v[a[i][cnt] - 1]);
			a[i][cnt] = 0;
			break;
		}
	}
	return;
}

pair<int, int> _move(int y, int x, int k){
	int velo, dir, size;
	tie(velo, dir, size) = v[k - 1];	
	
	while(velo--){
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		if(ny <= 0 || ny > n || nx <= 0 || nx > m){
			dir = (dir + 2) % 4;
			ny = y + dy[dir];
			nx = x + dx[dir];
		}
		y = ny;
		x = nx;
	}
	get<1>(v[k - 1]) = dir;
	
	return {y, x};
}
void moveFish(){
	memset(b, 0, sizeof(b));
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[i][j] != 0){
				int ny, nx;
				tie(ny, nx) = _move(i, j, a[i][j]);
				if(b[ny][nx] != 0){
					if(get<2>(v[b[ny][nx] - 1]) < get<2>(v[a[i][j] - 1])) b[ny][nx] = a[i][j];
				}else b[ny][nx] = a[i][j];
				a[i][j] = 0;
			}
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			a[i][j] = b[i][j];
		}
	}
	
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> k;
	for(int i = 1; i <= k; i++){
		cin >> r >> c >> s >> d >> z;
		if(d == 1) d = 0;
		else if(d == 2) d = 2;
		else if(d == 3) d = 1;
		else if(d == 4) d = 3;
		a[r][c] = i;
		v.push_back(make_tuple(s, d, z)); 
	}

	while(cnt < m + 1){
		cnt++;
		catchFish(cnt);
		moveFish();
	}
	cout << ret << "\n";
}

 

아무리 생각해도 코드 상에서 시간초과가 날 곳은 상어가 움직이는 while문밖에 없었는데... 문제의 조건을 다시보니, 상어의 최대 개수는 10000개, 속력은 1000이므로 벌써 10^7이다. 근데 이것이 낚시왕이 100번의 움직임을 보여줄 수 있으니 총 10^9으로 시간초과가 나는 것이 당연하다. 이걸 왜 문제를 읽고 고려를 안했을까? 참~ 버릇을 들여야하는데...

그렇다면 한칸 한칸씩 이동하는 것이 아닌 다른 아이디어를 써야할 것 같은데!

 

놀랍게도 이전에 들었던 강의에 있었던 내용 아닌가? 당시 강의를 들을 때 알고리즘 초보였던 내가 너무 어려운 문제여서 그냥 넘기는 바람에 풀었던 기억조차 안났다...ㅠ

 

코드는 기존의 위의 코드에서 속도에 대한 범위를 제한할 수 있도록하는 한 줄만 추가하면된다. 백준 질문게시판에 이 부분은 많이 답변이 되어있으니 궁금하다면 그곳을 참고해보자.