글 읽기 - 이문제 시간초과 어떻게 해결할수있나요..

minjae200 5년 전 0

나름대로 줄여보았는데도 시간초과가 나옵니다. 간단한 문제라 생각했는데 시간을 줄이는 방법이 생각나지 않습니다....

아이디어좀 주실분 계신가요

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

//N : 총 N개의 쓰레기
//M : 소각로 칸
//K : 쓰레기 종류
//Q : 명령횟수
int N, M, K, Q;

int main(void)
{
	scanf("%d%d%d%d", &N, &M, &K, &Q);
	int *road = new int[M + 1];
	queue <pair<int, int>> temp;
	for (int i = 0; i < N; i++) {
		int num; 
		scanf("%d", &num);
		temp.push(make_pair(num,1));
	}
	//소각로 세팅	
	int cnt = min(N, M);
	for (int i = 0; i < cnt; i++) {
		road[i] = temp.front().first;
		temp.pop();
	}
	for (int i = 0; i < Q; i++) {
		int tc; scanf("%d", &tc);
		switch (tc) {
		case 1:
			int L, R;
			scanf("%d %d", &L, &R);
			for (int i = L - 1; i <= R - 1; i++) {
				int pop_data = 0;
				if (temp.size() != 0) {
					pop_data = temp.front().first;
					temp.front().second--;
					if (temp.front().second == 0) temp.pop();
				}
				road[i] = pop_data;
			}
			break;
		case 2:
			int i; 
			scanf("%d", &i);
			printf("%d\n", road[i - 1]);
			break;
		case 3:
			int p, q;
			scanf("%d%d", &p, &q);
			temp.push(make_pair(p, q));
			break;
		case 4:
			int t;
			scanf("%d", &t);
			while (t!=0) {
				if (t >= temp.front().second) {
					t -= temp.front().second;
					temp.pop();
				}
				else {
					temp.front().second -= t;
					t = 0;
				}
			}
			break;
		}
	}
	for (int i = 0; i < M; i++)
		printf("%d ", road[i]);
	return 0;
}	

minjae200 5년 전 0

어떤 TC에 대해서 무한루프가 도는걸까요 아니면...스위치문에서 case 1에서 오래걸리는건가요 ㅠㅠ

jh05013 5년 전 0

최악의 경우 이 코드의 시간복잡도는 얼마일까요?

참고로 이 문제는 UCPC 2018 예선에서 가장 어려운 문제였습니다.

minjae200 5년 전 0

@jh05013

음ㅠㅠㅠㅠㅠ 시간초과뜰걸 예상은 했지만...잘모르겟습니다 ㅠㅠ

jh05013 5년 전 1

그래도 풀고자 하신다면, (p, q) pair를 만드는 것은 맞게 접근하셨습니다. 그런데 이 q개의 쓰레기를 road에 하나하나 집어넣으려고 하면 비효율적인 코드가 됩니다. 소각로 전체를 구현하지 말고 temp만으로 L번 쓰레기와 R번 쓰레기를 찾는 방법을 생각해 보세요.

jh05013 5년 전 1

저 코드의 문제점은 1번 쿼리의 시간복잡도가 O(R-L)이라는 것입니다. 그래서 전체 코드가 O(Q(R-L))이 되고, Q와 R-L의 최대값을 넣어 보면 시간초과가 나옵니다.

minjae200 5년 전 0

@jh05013 아!! 감사합니다. 알것같습니다. 감사합니다!!!

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

문제

문제

출처

ICPC

이문제 시간초과 어떻게 해결할수있나요..

minjae200 5년 전 0

minjae200 5년 전 0

jh05013 5년 전 0

minjae200 5년 전 0

jh05013 5년 전 1

jh05013 5년 전 1

minjae200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말