BOJ 17143 : 낚시왕

문제

---

문제 풀어보기

 

풀이

---

 

최근에 출제되는 삼성 기출문제는 거의 80% 가 시뮬레이션 문제입니다.

시뮬레이션은 순차적으로 진행되는 프로그램을 그대~로 구현하는 문제입니다.

 

 

이러한 문제들은 복잡한 알고리즘을 요구하지 않기 때문에

빠른 이해력과 정확한 설계만 한다면 대부분 푸실 수 있는 문제들입니다.

 

 

하지만 시뮬레이션에선 항상 시간 초과의 늪에 빠지게 됩니다.

이문제도 그랬는데요.

 

 

그러한 시간초과를 해결하는 방법이 바로 모듈러 연산입니다.

예를 들어 봅시다.

 

 

철이는 1초마다 숫자를 하나씩 증가하면서 말하고 있는데,

3의 배수일때마다 박수를 친다고 합니다.

그럼 1억초 이후에 철이는 몇 번 박수를 칠까요? 

 

 

라는 문제를 풀때 저희는

1초 일때 박수를 치는지 안치는지

2초 일때 박수를 치는지 안치는지

3초 일때 박수를 치는지 안치는지

다 계산하나요 ??

 

 

아닙니다.

그냥 1억을 3으로 나누면 반복적인 계산을 하지 않아도 됩니다.

이문제도 똑같습니다.

 

 

주석 '상어의 이동' 파트를 보시면

speedMod 라는 변수가 있습니다.

 

 

이것은 속도가 1000 인경우 최소 900번 이상의

무의미한 연산을 줄여주는 기능을 해주고 있습니다.

 

 

이 부분만 모듈러 연산으로 해결하신다면 다른 건 평이하게 푸실 수 

있으리라 생각합니다.

 

 

질문은 댓글에 ㅎㅎ

 

 

 

코드

---

#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <tuple>


int dx[] = { -1, 1 , 0 ,0 }; // 시계
int dy[] = { 0, 0, 1, -1 };

using namespace std;

int n, m, c;
int king;
int answer;

struct info
{
	int speed;
	int size;
	int dir;
};

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> c;

	// 상어정보
	map<pair<int, int>, info > mp; // x,y 값 = 속도,크기, 방향
	map<pair<int, int>, info >::iterator iter;
	map<pair<int, int>, info >::iterator iterEnd;

	for (int i = 1; i <= c; i++) {
		int a, b, s, d, z;
		cin >> a >> b >> s >> d >> z;
		mp[{a, b}] = { s,z ,d - 1 };
	}


	while (king < m) {

		//왕이 이동한다
		king++;


		// 가장 가까운 상어를 잡는다
		int targetX = n;
		int targetY = 0;

		iter = mp.begin();
		iterEnd = mp.end();
		for (iter; iter != iterEnd; iter++) {
			int x, y;
			tie(x, y) = iter->first;
			if (y != king) continue;
			if (x <= targetX) {
				targetX = x, targetY = y;
			}
		}
		if (mp.count({ targetX, targetY }) != 0) {
			answer += mp[{targetX, targetY}].size;
			mp.erase({ targetX, targetY});
		}


		// 상어의 이동
		map<pair<int, int>, info > mpNow;
		iter = mp.begin();
		iterEnd = mp.end();
		for (iter; iter != iterEnd; iter++) {
			int x, y, s, z, d;
			tie(x, y) = iter->first;
			d = iter->second.dir;
			s = iter->second.speed;
			z = iter->second.size;

			int speedMod = s;
			if (d == 0 || d == 1) {
				speedMod %= (n - 1) * 2;
			}
			else {
				speedMod %= (m - 1) * 2;
			}
			for (int i = 0; i < speedMod; i++) {
				x += dx[d];
				y += dy[d];
				if (x < 1 || x >= n+1 || y < 1 || y >= m+1) {
					x -= dx[d] * 2;
					y -= dy[d] * 2;
					if (d % 2 == 0) d += 1;
					else d -= 1;
				}
			}

			// 상어가 안겹친다면
			if (mpNow.count({ x,y }) == 0) {
				mpNow[{x, y}] = { s,z,d };

			} // 상어가 겹친다면
			else {
				if (mpNow[{x, y}].size >= z) {
					continue;
				}
				else {
					mpNow.erase({ x,y });
					mpNow[{x, y}] = { s,z,d };
				}

			}
		}

		mp = mpNow;
	}

	cout << answer << '\n';

	return 0;
}