글 읽기 - C++ 바로 시간초과 납니다..

reoy 3년 전 0

최악의 시간복잡도는 O(n(2m-1)) 아닌가요..? 아무리 생각해도 더 이상 시간을 못줄이겠어요.. 알고리즘은 맞는 것 같은데 바로 시간초과 나오네요ㅠㅠ

#include <stdio.h>
#include <vector>
using namespace std;
int main(void){
	int m,n,i,j,val,arr[3];
	scanf("%d%d",&m,&n);
	vector<int> left(m,1); //왼쪽 끝 1열 데이터 저장 
	vector<int> right(m-1,1); //나머지 데이터 저장 (맨 왼쪽 아닌 이상 column 같으면 값 같음) 
	for(i=0;i<n;i++){ //n번의 날 처리
		val=1;
		scanf("%d%d%d",&arr[0],&arr[1],&arr[2]);
		 
		for(j=arr[0];j<2*m-1;j++){ //0은 스킵 
			if(arr[val]==0){ //해당 횟수가 0이면 다음 횟수 진행 
				j--;
				val++;
				continue;
			}
			if(j<m) //맨 왼쪽 column 업데이트 
				left[j]+=val;
			else //맨 오른쪽 column 업데이트 
				right[j-m]+=val;
			arr[val]--;
		}
	}
	for(i=m-1;i>=0;i--){ //결과 출력. 거꾸로 저장돼있으므로 m-1부터 0까지 반복 
		printf("%d ",left[i]);
		for(j=0;j<m-1;j++)
			printf("%d ",right[j]);
		puts("");
	}
	return 0;
}

leinad2 3년 전 1

1초에 1억~5억의 연산량이 가능합니다. 저 시간복잡도로는 2초안에 돌기 힘들어 보이네요.

reoy 3년 전 0

방법 수정해서 해결했습니다. 감사합니다!

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

문제

문제

출처

ICPC

C++ 바로 시간초과 납니다..

reoy 3년 전 0

leinad2 3년 전 1

reoy 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말