백준 17143번 - 낚시왕(C++)

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

 

구현문제로 엄청난 사고력을 요하는 문제는 아니지만 시간 복잡도 때문에 수학적인 테크닉이 필요한 문제이다. 아무래도 구현문제이기 때문에 사람마다 풀이가 매우 다를 것이다. 하지만 기본적인 아이디어는 비슷할 것이다.

 

1. 낚시왕이 물고기를 낚는다.

2. 상어가 이동한다. 

 

그러므로 난 우선 처음 상어를 입력받을 때 사냥가능한 상어를 먼저 사냥하고 인덱스 1부터 솔루션을 시작했다. 그리고 상어의 정보를 담고 있는 벡터를 선언했는데, 상어가 사냥되거나 다른 상어에 의해 먹혔다고 해서 벡터에서 없애버리는 것은 구현이 어렵고 시간도 더 걸린다. 그래서 life 변수로 살았는지 죽었는지 체크해주었다.

 

또한 상어들을 이동하고서 같은 곳에 모두 쌓아놓고 이후 처리하는 것 보다, 도착할 때 마다 크기가 큰 상어의 정보로 업데이트해주는 것이 더 효율적이다. 

 

그리고 가장 중요한 것은 이동할 때 순수하나하나 이동하면 당연히 시간초과가 발생한다. 움직이는 모습을 보면 규칙이 꼭 있을 것 같다. 

 

크기가 5이고 2,2 에 존재하는 오른쪽으로 가는 상어가 있을 때, 자기 자신의 자리로 돌아오려면 몇이나 필요할까? 

8칸이 필요하다 그리고 여기서 8칸은 (5 - 1) / 2 와 같다.

즉, 좌우로 이동하는 상어는 (C - 1) / 2

상하로 이동하는 상어는 (R - 1) / 2 칸을 이동하면 자기 자신으로 돌아온다. 그러므로 만약 120칸을 이동하라고 했다면 

120 % 8 칸을 이동하는 것과 같다. 이 공식을 떠올리기 힘들어서 골드1을 받은 것이 아닌가 생각된다.

 

이것을 잘 고려해서 코드를 짜면 다음과 같다.

 

#include<iostream>
#include<vector>
using namespace std;

class shark{
public:
	int r,c,s,d,z;
	bool life;

	shark(){

	}

	shark(int r, int c, int s, int d, int z){
		this->r = r;
		this->c = c;
		this->s = s;
		this->d = d;
		this->z = z;
		this->life = true;
	}
};

int R, C, M;
vector<shark> sharkInfo;
int answer = 0;
int dx[] = {-1,1,0,0}; // 0 <-> 1 ,  2 <-> 3
int dy[] = {0,0,1,-1}; 

bool range(int x, int y){
	return x > -1 && x < R && y > -1 && y < C;
}

void solution(){
	int idx = 1;
	while(true){
		
		vector<vector<pair<int, int>>> sea(R, vector<pair<int, int>>(C, {-1 ,-1}));
		for(int i = 0; i < sharkInfo.size(); i++){
			if(sharkInfo[i].life){
				for(int j = 0; j < sharkInfo[i].s; j++){
					sharkInfo[i].r += dx[sharkInfo[i].d];
					sharkInfo[i].c += dy[sharkInfo[i].d];

					if(!range(sharkInfo[i].r, sharkInfo[i].c)){
						if(sharkInfo[i].d % 2 == 0) sharkInfo[i].d += 1;
						else sharkInfo[i].d -= 1;

						sharkInfo[i].r += dx[sharkInfo[i].d] * 2;
						sharkInfo[i].c += dy[sharkInfo[i].d] * 2;
					}
				}

				if(sea[sharkInfo[i].r][sharkInfo[i].c].second > sharkInfo[i].z){ // 갔는데 나보다 더 큰놈이 있음
					sharkInfo[i].life = false;
				}else{
					if(sea[ sharkInfo[i].r ][ sharkInfo[i].c ].first != -1){ // 나보다 작은놈인데 처음온게 아님
						sharkInfo[sea[ sharkInfo[i].r ][ sharkInfo[i].c ].first].life = false;
						sea[ sharkInfo[i].r ][ sharkInfo[i].c ].first = i;
						sea[ sharkInfo[i].r ][ sharkInfo[i].c ].second = sharkInfo[i].z;
					}else if(sea[ sharkInfo[i].r ][ sharkInfo[i].c ].first == -1){ // 처음옴
						sea[ sharkInfo[i].r ][ sharkInfo[i].c ].first = i;
						sea[ sharkInfo[i].r ][ sharkInfo[i].c ].second = sharkInfo[i].z;
					}
				}
			}
		}

		for(int k = 0; k < R; k++){
			if(sea[k][idx].first != -1){
				answer += sea[k][idx].second;
				//cout << " + " << sea[k][idx + 1].second;
				sharkInfo[sea[k][idx].first].life = false;
				break;
			}
		}
		idx++;

		if(idx == C) return;
	}
}

int main(){
	cin >> R >> C >> M;
	int Max = 101;
	int tmpI = -1;
	for(int i = 0; i < M; i++){
		int r,c,s,d,z;
		cin >> r >> c >> s >> d >> z;
		shark S(r - 1,c - 1,s,d - 1,z);
		sharkInfo.push_back(S);

		if(c - 1 == 0){
			if(Max > r - 1){
				Max = r - 1;
				tmpI = sharkInfo.size() - 1;
			}
		}
	}
	if(tmpI != -1) {
		sharkInfo[tmpI].life = false; 
		answer+=sharkInfo[tmpI].z;
	}

	solution();

	cout << answer << '\n';
}