글 읽기 - [나무 재테크] 시간초과 질문

zmaaq 5년 전 1

시간초과가 나서 질문드립니다.

처음에는 모든 나무를 하나의 리스트로 관리하였다가 실패해서

살아있는 나무와 죽은 나무를 분리해서 시도했지만 여전히 시간초과가 납니다.

다른 질문을 봤을 때 땅 별로 나무를 관리하면 해결된다는 답변을 보았는데

그렇게 관리했을 때에도 모든 나무에 대해서 체크가 필요하다고 생각하는데

어떤 차이가 있는지 궁금합니다.

또한 sort() 를 사용해서 나이순으로 정렬하는데 이게 시간초과의 원인이 될 수 있을까요?

혹시 그렇다면 다른 대안이 있는지 궁금합니다.

#include <cstdio>
#include <list>
#include <algorithm>
using namespace std;

struct Tree{
	int x;
	int y;
	int age;
	Tree(int _x, int _y, int _a): x(_x), y(_y), age(_a){}
	bool operator<(Tree other){
		return age < other.age;
	}
};

int n,m,k;
int A[11][11];
int map[11][11];
int tree_num[11][11];
int dir_x[8] = {0,1,1,1,0,-1,-1,-1};
int dir_y[8] = {-1,-1,0,1,1,1,0,-1};
list<Tree> alive;
list<Tree> dead;

void spring(){
	for(auto it=alive.begin(); it!=alive.end(); ++it){
		Tree t = *it;
		
		if(map[t.y][t.x] >= t.age){
			map[t.y][t.x] -= t.age;
			it->age += 1;
		}else{
			dead.push_back(t);
			alive.erase(it--);
		}
	}
}

void summer(){
	for(auto it=dead.begin(); it!=dead.end(); ++it){
		Tree t = *it;
		
		map[t.y][t.x] += t.age/2;
		tree_num[t.y][t.x] -= 1;
	}
	dead.clear();
}

void fall(){
	list<Tree> cur = alive;
	for(auto it=cur.begin(); it!=cur.end(); ++it){
		Tree t = *it;
		
		if(t.age%5 != 0) continue;
		
		for(int i=0; i<8; i++){
			if(t.x+dir_x[i] < 1 || t.x+dir_x[i] > n)
				continue;
			if(t.y+dir_y[i] < 1 || t.y+dir_y[i] > n)
				continue;
			
			tree_num[t.y+dir_y[i]][t.x+dir_x[i]] += 1;
			alive.push_back(Tree(t.x+dir_x[i],t.y+dir_y[i],1));
		}
	}
}

void winter(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			map[i][j] += A[i][j];
		}
	}
}

bool all_die(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(tree_num[i][j] > 0) return false;
		}
	}
	
	return true;
}

int main() {
	scanf("%d %d %d\n", &n, &m, &k);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			scanf("%d", &A[i][j]);
			map[i][j] = 5;
		}
	}
	for(int i=0,x,y,age; i<m; i++){
		scanf("%d %d %d", &y, &x, &age);
		tree_num[y][x] += 1;
		alive.push_back(Tree(x,y,age));
	}

	for(int year=0; year<k; year++){
		if(all_die()){
			printf("0");
			return 0;
		}
		
		alive.sort();
		spring();
		summer();
		fall();
		winter();
	}
	
	printf("%d", alive.size());
	
	return 0;
}

seico75 5년 전 1

50번째줄 복사가 시간이 많이 걸리는 것 같습니다.

한번 소트하고 나면 새로운 나무는 앞에 넣으면 되고..

기존 나무는 나이가 1살 먹거나 죽으니까(erase) 소트상태는 유지되니 sort 도 처음 한번만 하고

fall 에도 복사하지 말고 그냥 원본에 앞에 넣으면 전체 결과에 영향을 주지 않을 것 같습니다.

그래도 각 셀별로 관리하는 것보다 많이 느린 것 같네요.

zmaaq 5년 전 0

우와 감사합니다!!

일단 얘기해주신대로 하니 해결되었습니다.

그런데 셀별로 관리했을 때가 그러지 않았을 때보다 어떤 부분에서 빨라질 수 있나요?

저는 계속 셀별로 관리를 한다해도 체크를 하지 않고 건너뛸 수 있는 나무는 없다고 생각되어서

모든 나무를 체크해도 다른 부분에서 빨라질 수 있는 요소가 있는 건지

아니면 제가 생각 못한 건너뛸 수 있는 부분이 있는지 궁금합니다.

seico75 5년 전 0

저도 궁금해서 어제 몇가지 테스트해보다가 잠들었는데.. 아직은 잘 모르겠네요.

각 셀로 했을 때는 저는 deque 를 썼습니다.

그래서 전체를 deque 로 만들어서 자료구조 때문인지를 해보려다가 구조적인 차이로 못해봤습니다.

deque 로 각 쎌별로 처리할 경우는 한번 나무가 죽기 시작하면 그 뒤는 다 pop_back() 해버릴 수 있어서 시간절약이 되는건지..

기본적으로 list 가 deque 보다 overhead 가 있어서 그런건지..

zmaaq 5년 전 0

그렇군요 ㅠ

답변해주셔서 감사합니다!!

heyuns2 5년 전 2

저도 리스트로 해서 자꾸 시간초과 뜨길래 각 칸을

0, 1, 2, 3, 4

5, 6, 7, 8, 9

이런 식으로 순번을 붙여서 해쉬맵 HashMap<Integer, List<Integer>>로 상수시간으로 접근 후 나무별로 리스트를 관리해줬더니 통과했습니다..

그리고 list에서 죽은 나무들을 remove하지 않고 살아서 성장한 나무들만 새로 리스트를 만들어서 아예 리스트를 교체해줬습니다.

remove가 삭제하는데 O(n)이 걸려서 오버가나나 하고요!

저도 실력이 부족한지라 답변 잘 안다는데 삼성 문제중에 시간초과 문제들이 자주 발생하는 것 같아 해쉬맵을 우선적으로 적용해봐야하지 하고 깨닫게 되어서 이렇게 댓글남깁니다

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

문제

문제

출처

ICPC

[나무 재테크] 시간초과 질문

zmaaq 5년 전 1

seico75 5년 전 1

zmaaq 5년 전 0

seico75 5년 전 0

zmaaq 5년 전 0

heyuns2 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말