글 읽기 - 시간초과 .. 왜이럴까요

malmang 5년 전 0

답은 맞게 나오는것같은데 시간초과가 계속뜨네요ㅜ 시간초과의 원인이 뭘까요?

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
int main() {
	int n, m, h,max;
	vector<int> tree;
	vector<pair<int, int>> cut;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> h;
		tree.push_back(h);
	}
	sort(tree.begin(), tree.end());
	max = tree.back();
	
	for (int i = max; i > 0; i--) {
		int sum = 0;
		for (int j = 0; j < tree.size(); j++) {
			int block=  tree[j] -i;
			if (block < 0) {
				block = 0;
			}
			sum =sum+ block;
		}
		cut.push_back(make_pair(i, sum));
		if (sum >= m) {
			break;
		}
		
		//cout << cut.back().first<<cut.back().second;
	}
	cout << cut.back().first;

}

dlwocks31 5년 전 1

나무의 높이는 최대 10⁹이기 때문에 19줄에 있는 for loop에서 당연히 시간초과가 납니다. 참고로 일반적인 컴퓨터에서 1초동안 수행할 수 있는 연산은 10⁸회 입니다. 다른 알고리즘을 생각해보세요.

djm03178 5년 전 1

요즘 컴퓨터의 속도로는 10^9 이상의 연산도 가능하지만, 그 연산이 매우 단순할 때의 이야기고 여기서는 한 번의 루프에 많은 작업을 하기 때문에 매우 오래 걸립니다.

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

문제

문제

출처

ICPC

시간초과 .. 왜이럴까요

malmang 5년 전 0

dlwocks31 5년 전 1

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말