글 읽기 - [C++] 1715번 문제 질문입니다!! 제발 도와주세요..

eastho0116 2년 전 0

정말 많이 시도 해봤는데... 제 수준에서는 어느정도로 연산을 더 줄여야 시간초과가 안 나는지 모르겠습니다...

도움이 절실히 필요합니다...ㅜㅜㅜ

#include<iostream>
#include<algorithm>
using namespace std;

int main(void) {
	int cnt = 0;
	cin >> cnt;
    
	int* list = new int[cnt];
	int ans = 0;
    
	for(int i = 0; i < cnt; i++)
		cin >> list[i];
	
	for(int i = 0; i < cnt - 1; i++){
		sort(list + i, list + cnt);
		list[i + 1] += list[i];
		ans += list[i + 1];
	}
    
	cout << ans;
    
}

0000000000 2년 전 1

가장 작은 두 개씩 합하는 방법은 맞습니다만 for문 에서 매번 sort를 하고 있기 때문에 시간복잡도가 O(N²logN)이 되어 시간초과를 피할 수 없습니다. priority_queue를 써 보세요.

eastho0116 2년 전 0

도와주셔서 정말 감사합니다..ㅠㅠㅠ

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

문제

문제

출처

ICPC

[C++] 1715번 문제 질문입니다!! 제발 도와주세요..

eastho0116 2년 전 0

0000000000 2년 전 1

eastho0116 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말