글 읽기 - 시간초과 납니다 ㅠㅜㅜ

pms940725 3년 전 0

최대 중첩이라고 해봐야 2중 포문정도이고, vector 삭제하는데 시간 많이 잡아먹는거같아서 없애고 하는데도 시간초과가 뜨네요 ㅠㅜ

자료구조를 다른걸 써야 하는건가요.. 아니면 쓸데없는게 많이 들어간걸까요..?

#include <stdio.h>
#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;
int N, M, K;

int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };

typedef struct{
	int x, y;	//위치
	int m;	//질량
	int s;	//속도
	int d;	//방향
}FIREBALL;

vector<FIREBALL> fireball;
vector<int> map[50 + 10][50 + 10];

void input() {
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		FIREBALL tmp;
		cin >> tmp.y >> tmp.x >> tmp.m >> tmp.s >> tmp.d;
		tmp.x--;
		tmp.y--;
		fireball.push_back(tmp);
	}
}

void printFireball() {
	for (FIREBALL tmp : fireball) {
		cout << tmp.x<<" "<< tmp.y<<" "<< tmp.m<<" "<< tmp.s<<" "<< tmp.d<< endl;
	}
}

void printMap() {
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cout << map[y][x].size() << " ";
		}
		cout << endl;
	}
}

void move() {
	for (FIREBALL &tmp : fireball) {
		int nx = tmp.x + tmp.s*dx[tmp.d];
		int ny = tmp.y + tmp.s*dy[tmp.d];

		if (nx < 0) {
			nx = N + nx%N;
		}
		if (nx >= N) {
			nx = nx%N;
		}
		if (ny < 0) {
			ny = N + ny%N;
		}
		if (ny >= N) {
			ny = ny%N;//영역을 벗어났을 때 되돌아오는 것은 나누기가 아니라 모듈러란다 바보야
		}
		
		tmp.x = nx;
		tmp.y = ny;
	}
}

void addMap() {
	for(int i=0; i<fireball.size(); i++){
		FIREBALL tmp = fireball[i];
		map[tmp.y][tmp.x].push_back(i);
	}
}

void clearMap() {
	memset(map, 0, sizeof(map));
}

bool checkDir(vector<int> list) {
	int chk = list[0] % 2;
	for (int d : list) {
		if (chk != d % 2)
			return false;
	}
	return true;
}

void merge(int x, int y) {
	vector<int> list = map[y][x];
	vector<int> d_vec;
	int m=0, s=0, d=0;
	for (int i : list) {
		m += fireball[i].m;
		s += fireball[i].s;
		fireball[i].m = 0;
		d_vec.push_back(fireball[i].d);
	}

	int new_m = m / 5;
	int new_s = s / list.size();

	if (new_m == 0)
		return;

	FIREBALL tmp[4];
	for (FIREBALL &t : tmp) {
		t.x = x;
		t.y = y;
		t.m = new_m;
		t.s = new_s;
	}

	if (checkDir(d_vec)) {
		tmp[0].d = 0;
		tmp[1].d = 2;
		tmp[2].d = 4;
		tmp[3].d = 6;
	}
	else {
		tmp[0].d = 1;
		tmp[1].d = 3;
		tmp[2].d = 5;
		tmp[3].d = 7;
	}

	for (FIREBALL t : tmp) {
		fireball.push_back(t);
	}
}

void checkMap() {
	for (int i = 0; i < fireball.size(); i++) {
		FIREBALL tmp = fireball[i];
		if (map[tmp.y][tmp.x].size() < 2) continue;
		if (fireball[i].m == 0) continue;
		merge(tmp.x, tmp.y);
	}
}

void removeFireball() {
	for (int i = 0; i < fireball.size(); i++){
		if (fireball[i].m == 0){
			fireball.erase(fireball.begin() + i);
			i--;
		}
	}
}

int getMess() {
	int sum = 0;
	for (FIREBALL t : fireball) {
		sum += t.m;
	}
	return sum;
}

int sol() {
	for (int i = 0; i < K; i++) {
		clearMap();
		move();
		addMap();
		checkMap();
		//removeFireball();
	}
	return getMess();
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(NULL);

	input();

	cout << sol();
	return 0;
}

ygj02054 3년 전 0

저도 처음에 이런방식으로 풀었다가 시간초과 떴는데.. struct에는 위치를 저장하지 않고, map[][][] 3차원벡터로 map[r][c].push_back(FIREBALL{m,s,d}) 이런 방식으로 풀어보세요! 이 방식으로 바꾸니까 16ms 뜨네요

pms940725 3년 전 0

댓글 감사합니다. 질문 하나만 더드려도 될까요.

그렇다면 fireball을 move할 때 map[][]을 순회하는 방식으로 접근하는 건가요??

tkstka0023 3년 전 0

확실하진 않지만 92번째 줄에

vector list = map[y][x];

하는 부분에서 벡터 복사가 이뤄져서 시간을 잡아먹는게 아닐까 싶습니다.

vector& list = map[y][x]; 이렇게 참조 형태로 바꿔보세요.

그리고 d_vec를 check_dir 한테 던져줄 때도 마찬가지로 벡터 복사가 발생하는것 같네요.

82번째 줄에 checkDir 함수의 매개변수를 vector& list로 바꿔보세요.

ygj02054 3년 전 0

그렇다면 fireball을 move할 때 map[][]을 순회하는 방식으로 접근하는 건가요??

--> 네 맞습니다.

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

문제

문제

출처

ICPC

시간초과 납니다 ㅠㅜㅜ

pms940725 3년 전 0

ygj02054 3년 전 0

pms940725 3년 전 0

tkstka0023 3년 전 0

ygj02054 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말