글 읽기 - 시간 초과 질문드립니다

sta48 4년 전 0

예제 테스트케이스는 올바르게 통과하는데

시간초과 에 걸립니다

처음에 벡터를 이용해서 std 라이브러리 sort 시켰는데

시간초과가 나서 dequeue 이용하였고,

- 번식한 나이1 나무들은 push_front()

- 1살씩 나이가 증가하는 나무들은 push_back()

하도록 구현하여

나이가 가장 적은 나무들이 먼저 양분을 먹도록 구현하였습니다

정렬 부분을 제외시켰는데도 시간초과가 났는데

혹시 tuple 사용으로 인해 복잡도가 올라간걸까요?

나무 구조체를 사용하나 tuple을 사용하나

메모리 사용량의 차이일 뿐

복잡도는 똑같을 것이라고 생각하여

tuple로 구성하였거든요

아니면

Line 109, 114, 124, 129 처럼

각 함수 내에서 Global로 선언한 queue나 dequeue를 최신화 시키는 부분에

대입연산으로 인해 복잡도가 올라간걸까요?

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <tuple>
#include <algorithm>
//#include <filesystem>

using namespace std;

queue<tuple<int, int, int>> dead;
deque<tuple<int, int, int>> q;

int nutri[11][11] = { 0, }; // 겨울에 추가되는 양분 입력받는 배열
int map[11][11] = { 0, }; // 땅 양분 맵
int dirx[8] = { 1, 1, 0, -1, -1, 0, -1, 1 };  // 8방향 번식을 위한 좌표
int diry[8] = { 0, 1, 1, 0, -1, -1, 1, -1 };

void spring(int N, int M);
void summer(int N, int M);
void fall(int N, int M);
void winter(int N);

int main(void) {

	/*FILE* fin = fopen("input.txt", "r");
	FILE* fout = fopen("output.txt", "w");*/

	int N = 0; // 맵 크기
	int M = 0; // 심은 나무 개수
	int K = 0; // 종료되는 조건
	int x = 0; // 나무좌표x
	int y = 0; // 나무좌표y
	int z = 0; // 나무나이

	scanf("%d", &N);
	//fscanf(fin, "%d", &N);
	scanf("%d", &M);
	//fscanf(fin, "%d", &M);
	scanf("%d", &K);
	//fscanf(fin, "%d", &K);

	/* 1. 겨울에 추가되는 양분의 양 맵에 입력 */

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d ", &nutri[i][j]);
			//fscanf(fin, "%d ", &nutri[i][j]);
		}
		scanf("\n");
		//fscanf(fin, "\n");
	}

	/* 2. 심은 나무 좌표와 나무 나이 입력받고 맵 양분 5로 초기화 */

	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &x, &y, &z);
		//fscanf(fin, "%d %d %d", &x, &y, &z);
		q.push_back(make_tuple(x, y, z));
		scanf("\n");
		//fscanf(fin, "\n");
	}

	for (int i = 1; i <= N; i++) {  // 초기 양분 5로 셋팅
		for (int j = 1; j <= N; j++) {
			map[i][j] = 5;
		}
	}

	/* 3. 사계절 동작 */

	while (K--) {
		// 봄 : 나이가 적은녀석부터 양분 먹기, 못먹은 놈은 죽은 놈으로 체크
		// 여름 : 죽은 나무 체크해서 땅에 양분이 되도록
		// 가을 : 맵 벗어나지 않는 범위에서 나이1로 8방향 번식
		// 겨울 : 초기 입력받은 양분을 SCDC? 기계가 양분 추가

		spring(N, M);
		summer(N, M);
		fall(N, M);
		winter(N);
	}
	printf("%d", q.size());
	//fprintf(fout, "%d", q.size());

	return 0;
}

void spring(int N, int M) {
	deque<tuple<int, int, int>> res;  // 결과값 반환을 위한 큐

	while (!q.empty()) {
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		int z = get<2>(q.front());
		
		if (map[x][y] - z >= 0) {
			map[x][y] -= z; // 나이만큼 양분을 먹고
			z++;  // 나이 1증가
			res.push_back(make_tuple(x, y, z)); // 양분을 먹고 죽지 않는 나무만 결과반환 큐에 저장
		}
		else {  // 양분을 못먹는 나무는 죽고 죽은 나무를 양분으로 만들기
			dead.push(make_tuple(x, y, z));
		}
		q.pop_front();
	}
	q = res;
}

void summer(int N, int M) {
	queue<tuple<int, int, int>> res;
	res = dead;
	// dead 큐에 있는 죽은 나무를 양분으로 만들고 dead 큐 비우기
	while (!res.empty()) {
		int x = get<0>(res.front());
		int y = get<1>(res.front());
		int z = get<2>(res.front());

		map[x][y] += (int)(z / 2);
		res.pop();
	}
	dead = res; // dead큐 최신화
}

void fall(int N, int M) {
	deque<tuple<int, int, int>> tmp;
	tmp = q;

	while (!tmp.empty()) {
		int x = get<0>(tmp.front());
		int y = get<1>(tmp.front());
		int z = get<2>(tmp.front());

		if (z != 0 && z % 5 == 0) { // 나무 나이가 5의 배수일 때
			for (int i = 0; i < 8; i++) {
				int nx = x + dirx[i];
				int ny = y + diry[i];

				if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
					q.push_front(make_tuple(nx, ny, 1)); // 나이 1로 번식
				}
			}
		}
		tmp.pop_front();
	}
}

void winter(int N) {  // SCDC기계가 양분 추가
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			map[i][j] += nutri[i][j];
		}
	}
}

bupjae 4년 전 2

dequeue 대입연산 (= 데이터 전체 복사) 이 생각보다 시간을 많이 소모한 것으로 보입니다.

이 프로그램에서 대입연산의 횟수를 최소화하도록 수정한 후 제출한 코드가 '맞았습니다'를 받았습니다.

109번째 줄에서, 데이터 전체 복사하는 것 보다는 q와 res가 들고 있는 내용을 서로 바꾸는 것이 더 효율적입니다.

q.swap(res) 를 사용해 보세요.

summer 함수에서는 res = dead 로 복사한 후 res 의 원소를 순서대로 삭제만 했을 뿐 다른 조작을 하지 않은 채로

dead = res 로 비어있는 res 를 dead 로 복사하고 있습니다.

이 경우는 res 를 사용할 필요 없이 dead를 직접 이용할 수 있습니다.

fall 함수에서는 tmp 에 복사한 후 tmp의 내용에 따라 q 의 내용이 달라지고 있습니다.

이 경우에는 복사를 피하는 방법이 없지는 않지만 적용하기 매우 까다로우므로 그냥 냅두는 것이 좋을 것 같습니다.

sta48 3년 전 0

감사합니다 spring 함수에서

swap함수를 사용하니 바로 해결됐어요

아무래도 최악의 경우에서

복잡도가 크게 올라갔었나봐요

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

문제

문제

출처

ICPC

시간 초과 질문드립니다

sta48 4년 전 0

bupjae 4년 전 2

sta48 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말