글 읽기 - 16235(나무재테크, C++) 아무리 줄여도 계속 시간초과가 납니다..

jhim000 4년 전 1

vector로 구현을 시작해서 이왕 한 거 최대한 시간을 줄여서라도 정답처리를 받으려 했는데 도무지 안 됩니다 ㅠ

여기서 갈아엎고 dqueue로 구현하는 방법 이외에 좋은 방법이 없을까요?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef struct tree {
	int y, x, z; // 나무의 위치, 나무의 나이
}tree;
bool cmp(tree t1, tree t2) {
	if (t1.y == t2.y && t1.x == t2.x) return t1.z < t2.z;
	else return t1.x < t2.x;
}
int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int x_pos, y_pos, old;
int N, M, K;
int A[10][10]; 
int map[10][10];
vector<tree> T; // 처음에 심은 나무의 정보
int main(void) {
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);	map[i][j] = 5;
		}
	}
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &x_pos, &y_pos, &old);
		T.push_back({ y_pos - 1, x_pos - 1, old });
	} 
	// 셋팅 완료

	while (K--) { // K년 동안 반복
		vector<tree> D; // 죽은나무
		vector<tree> birth; // 새로 태어난 나무
		
		// 1. 봄
		sort(T.begin(), T.end(), cmp);
		for (int c = 0; c < T.size(); c++) {
			if (T[c].z <= map[T[c].y][T[c].x]) { // 나무: 양분 먹고
				map[T[c].y][T[c].x] -= T[c].z;
				T[c].z++;
				
				// 가을에 새로 태어날 나무도 미리 birth에 담아둔다.
				if (T[c].z % 5 == 0) {
					for (int i = 0; i < 8; i++) {
						int y = T[c].y + dy[i];
						int x = T[c].x + dx[i];
						if (0 > y || y >= N || 0 > x || x >= N)	continue;
						birth.push_back({ y, x, 1 });
					}
				}
			}
			else { // 땅에 양분이 없어서 양분을 못먹음 --> 바로 죽음
				D.push_back(T[c]);
				T.erase(T.begin() + c);
				c--;
			}
		}
		for (int i = 0; i < D.size(); i++) map[D[i].y][D[i].x] += D[i].z / 2; // 2. 여름
		for (int i = 0; i < birth.size(); i++) T.push_back(birth[i]);		  // 3. 가을
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) map[i][j] += A[i][j]; // 4. 겨울
	}
	cout << T.size();
	return 0;
}

seico75 4년 전 2

1000년까지 돌기 때문에 나무수가 엄청 많아 질 수 있고, 이때 sort 가 들어가면 시간초과가 나올 것 같습니다.

sort 가 들어가는 것을 막기 위한 방법이 있어야 합니다.

새로 생기는 나무는 항상 1살이고 죽는 나무는 같은 위치의 산 나무 보다 나이가 많기 때문에

각 위치별로 deque 를 만들어서 앞에서 새나무 넣고 뒤에서 죽은 나무 빼는 것이 가장 간단하겠지만....

굳이 vector 를 쓰고 전체 나무를 하나의 vector 에서 관리한다면 아래 링크와 같이 가능할 것 같습니다.

https://ideone.com/7hIIcu

Vector 를 두개를 사용해서 새 나무 뒤에 죽은 나무 빼고 넣으면 처음 한번만 소트하면 될 것 같습니다.

그리고 문제의 x, y 는 r, c 로 작성하신 코드에서는 바뀐 것 같습니다.

jhim000 4년 전 0

귀한 시간 내어주셔서 감사합니다!!

beomyoung93 2년 전 0

@seico75

'sort 가 들어가는 것을 막기 위한 방법이 있어야 합니다.

새로 생기는 나무는 항상 1살이고 죽는 나무는 같은 위치의 산 나무 보다 나이가 많기 때문에..'

이부분에서 힌트를 얻어서

애기나무 앞에 넣고, 죽은 나무 정렬에 신경써서 sort() 호출을 줄였더니

1%-시간초과에서 43%-시간초과로 개선되었습니다.

감사합니다!

seico75 2년 전 2

제가 말씀드린 것은 sort를 없애는 것이었습니다.

초기에 한 장소에 2개 이상의 나무가 배치될 수 있으니 초기값에 대해서는 sort 를 해야겠지만..

그 이후 매년 돌릴 때에는 sort 를 안 쓸수 있습니다.

앞에 새로운 나무를 넣고, 죽은 나무는 제거해 놓으면 sort 함수를 지울 수 있을 것 같습니다.

- 그리고.. 정렬이 되어 있으니 나무가 죽기 시작하면 뒤는 다 죽겠죠?

- 죽는 나무는 제거했으면 굳이 죽은 나무 여부를 확인할 필요도 없을 것 같습니다.

beomyoung93 2년 전 0

@seico75

하나는 알고, 둘은 몰랐습니다..

정렬은 한 번만 하고 아기나무를 계속 앞에 넣으면, 정렬을 반복하지 않아도 순서가 유지되네요.

덕분에 아침부터 헤매던 문제가 풀렸습니다 ㅠㅠ

피드백 정말 감사합니다!!!!!

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

문제

문제

출처

ICPC

16235(나무재테크, C++) 아무리 줄여도 계속 시간초과가 납니다..

jhim000 4년 전 1

seico75 4년 전 2

jhim000 4년 전 0

beomyoung93 2년 전 0

seico75 2년 전 2

beomyoung93 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말