34. [백준 20056번 / C++] 마법사 상어와 파이어볼

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

20056번: 마법사 상어와 파이어볼

 

삼성 서탈...해서 꺾여가지고 지금까지 안풀었던건 아니고, LG 인적성이 급해서 코테를 잠시 쉬었습니다.

 

인적성... 준비한다고 했는데 솔직히 모르겠어요. 그냥 잘보기를 기도하도록 하겠습니다.. 비록 감기에 걸렸지만..

 

+ 블로그글을 의식하지않고 그냥 올렸어서 몰랐는데 말투가 좀 이상해서 바꾸겠습니다.

 

이제 문제를 보도록하죠. 늘 그렇듯 상어입니다.

 

문제 조건은 모두 읽어보시면 아실 거고, 제가 틀렸을 때 반례가 됐던 부분을 설명해드리면

 

1. 속도에 대한 모듈러 연산은 필수지만 파이어볼을 합칠 때는 모듈러 연산이 된 S를 합해선 안된다. (문제 조건에 의거)

2. 비트마스킹을 이용해 모두 짝수, 모두 홀수를 계산하는 것은 반례가 있다.

3. 합쳐졌다가 4개로 분리되는 파이어볼은 이동하는 것이 아니다. 그 자리에 그대로 있다.

 

아마 대부분은 이 세 가지에서 해결하지 못하고 틀리실 것이라 생각합니다. 왜냐하면 제가 그랬기 때문에....

 

바로 코드를 보죠.

 

#include<bits/stdc++.h>
using namespace std;
const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, m, k, r, c, fm, s, d, ret;
struct ball{
	int m, s, d, os;
};
vector<ball> a[54][54];

void goFire(){
	vector<ball> b[54][54];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(a[i][j].size()){
				for(int h = 0; h < a[i][j].size(); h++){
					int ny = (i + dy[a[i][j][h].d] * a[i][j][h].s + n) % n;
					int nx = (j + dx[a[i][j][h].d] * a[i][j][h].s + n) % n;
					
					b[ny][nx].push_back({a[i][j][h].m, a[i][j][h].s, a[i][j][h].d, a[i][j][h].os});
				}
			}
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(b[i][j].size() >= 2){
				int tempM = 0, tempS = 0, even = 1, odd = 1;
				for(int h = 0; h < b[i][j].size(); h++){
					tempM += b[i][j][h].m;
					tempS += b[i][j][h].os;
					if(b[i][j][h].d % 2 == 0) odd = 0;
					else even = 0;
				}
				
				tempM /= 5;
				tempS /= b[i][j].size();
				
				b[i][j].clear();
				if(tempM == 0) continue;
				
				for(int h = 0; h < 4; h++){
					if(odd || even) b[i][j].push_back({tempM, tempS % n, h * 2, tempS});
					else b[i][j].push_back({tempM, tempS % n, h * 2 + 1, tempS});
				}
			}
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			a[i][j] = b[i][j];
		}
	}
	return;
}
int main(){
	cin >> n >> m >> k;
	for(int i = 0; i < m; i++){
		cin >> r >> c >> fm >> s >> d;
		r--; c--;
		a[r][c].push_back({fm, s % n, d, s});
	}
	for(int i = 0; i < k; i++){
		goFire();
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(a[i][j].size()){
				for(int h = 0; h < a[i][j].size(); h++){
					ret += a[i][j][h].m;
				}	
			} 
		}
	}
	cout << ret << "\n";
}

 

코드를 보면 S의 모듈러 연산값과 그렇지 않은 orignal 속도(=os)를 struct에 모두 넣어 처리했습니다.

모두 홀수 혹은 짝수인가를 판단하는 것은 한 번이라도 짝수 혹은 홀수라면 odd, even 변수가 false가 되게 설정하여 구분했습니다.

파이어볼의 이동은 b라는 새로운 배열에 이동과 분열을 구현했다가 다시 a로 뒤집어 씌우는 형태로 구현했습니다.

 

 

참고로 LG 코테가 코앞인데 왜 삼성을 준비하냐고 하시면... 그냥 구현이 나올 것 같아서? 입니다.

저번에 채용연계형 코테는 합격했었기 때문에 구현만 조심하면 괜찮을 것이라 생각해서이기도 합니다... 어찌됐든 끝까지 한 번 가보겠습니다.