강의로 돌아가기
김현태

효율성 테스트.

//#include
//#include
//#include
//#include

using namespace std;

long long solution(int n, vector works) {
long long answer = 0;

for(int i = 0; i < n; i++) {
    vector<int>::iterator it = max_element(works.begin(), works.end());
    if(*it != 0) {
        *it = *it -1;
    }
}

int fatigue = 0;
for(vector<int>::iterator it = works.begin(); it!= works.end(); it++) {
    fatigue += pow(*it, 2);
}
answer = fatigue;
return answer;

}

테스트는 모두 통과했는데, 효율성 테스트를 못 넘네요.
stl을 기반으로 한 매우 정제된 코드인데, 효율성을 못 넘는다면, 다른 접근법이 있다는 이야기 같은데, 혹시 아시는분.

  • 마지환
    max_element를 찾는게 혹시 배열 전체를 다 찾는건가요 ? 마지환 2018.08.22 21:10
  • 마지환
    저는 산술 기하 평균의 확장으로 a^2+b^2>=2ab 라는 식을 확장해서 가장 평탄?할때 제곱의 최소값을 갖는다는 사실을 우선 첫번째로 생각했습니다. 여기까지는 아마 똑같은 풀이 같네요. 저는 해당 문제를 해결하기 위해 우선 순위 큐를 사용하여 가장 큰 값을 top에서 꺼낸 후 하나를 감소시켜서 다시 넣는 방법을 사용했어요! 마지환 2018.08.22 21:11
  • 마지환
    이 방법은 NlogN 의 효율성을 가집니다~~ 마지환 2018.08.22 21:12
  • 신두철
    저는 구간 트리로 풀었는데 초기화에 N, 최대값찾는데 1, 업데이트 하는데 logN을 전부 따로 돌려서 통과할 줄 알았더니 아직도 효율성 못넘어가네요 ㅠㅠ 신두철 2018.09.04 21:03
1 개의 답변
hacksg

새로 문제가 개편되고 위 방법으로는 못풀게 됐습니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.