글 읽기 - 시간초과때문입니다.

yujjjang 6년 전 0

시간 초과가 됩니다. 50% 에서 바뀌더군요.

무한 루프에 빠져들어서 시간초과가 되는건지.. 확인하고 있는데 무엇이 잘못되었는지 경우를 찾을수가 없어요.. 방법도 잘 모르구요

혹은 알고리즘 문제로 시간이 너무 오래걸려서 해결하지 못하는 거라면 혹시 문제점을 지적해주실수 있으신가요?

공부를 시작한지가 얼마되지않아서 아는게 없네요..ㅠ

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//퀵소트 정렬.
void QuickSort(vector<long long>& arr,long long left, long long right) {
  long long i = left;
  long long j = right;
  long long pivot = arr[(left+right)/2];

  do{
    while(arr[i] < pivot) i++;
    while(arr[j] > pivot) j--;

    if (i<=j){
      swap(arr[i], arr[j]);
      ++i;
      --j;
    }
  } while ( i<= j);

  if (left < j) QuickSort(arr, left, j);
  if (i < right) QuickSort(arr, i, right);
}

// Calc 함수는 value 로 짤랐을때 얻을 수 있는 나무 길이의 합을 리턴합니다.
long long Calc(vector<long long>& arr, long long value) {
  long long sum = 0;
  for(unsigned int i = 0; i < arr.size(); ++i) {
    if (arr[i] > value) {
        sum += (arr[i] - value);
    }
  }
  return sum;
}
// Calcc 함수는 Solving 에서 정확한 값을 구하지 못한경우
// 재귀함수로 하나씪 줄여가며 주어진 길이보다 길어지는 최초의 값을 리턴합니다.
long long Calcc(vector<long long>& arr, long long end, long long key) {
    long long tmp = Calc(arr, end);
    if (tmp < key) return Calcc(arr, end - 1, key);
    else return end;
}

// Solving 함수는 이진탐색으로 제일 작은값과 제일 큰값을 기준으로 
// 중간값을 찾으며 움직입니다.
// 못찾은 경우 Calcc 함수를 호출합니다.
long long Solving(vector<long long>& arr, long long start, long long end,
    long long key) {
  long long mid = start + (end - start) /2;

  long long tmp;
  while (start <= end) {
    tmp = Calc(arr, mid);
    if (tmp == key) return mid;
    else if (tmp > key) {
      start = mid + 1;
      mid = start + (end - start) / 2;
    } else {
      end = mid - 1;
      mid = start + (end - start) / 2;
    }
  }

    return Calcc(arr, end, key);
}

int main(){
  int num;
  vector<long long> ca;
  long long tmp;
  long long height;
  cin >> num;
  cin >> height;
  while(num--){
    cin >> tmp;
    ca.push_back(tmp);
  }
  QuickSort(ca, 0, ca.size() -1);

  tmp = Solving(ca, ca[0], ca.back(), height);

  cout << tmp << endl;

  return 0;
}
// 감사합니다.
                                                                                      //

chogahui05 6년 전 1

재귀함수로 하나씩 줄여가면서 답을 만족하는 가장 작은 값을 리턴하게 하면

그냥 탐색하는 것이랑 다른 게 무엇인지 잘 모르겠습니다.

예를 들어서;

1 3 4 5 6 7 11 12 14 16 17 23 27 ... 100222

이런 데이터가 있습니다.

이 중에 9라는 데이터는 없습니다. 이진 탐색으로도 당연히 안 찾아지는 데이터입니다.

그러면 100222부터 탐색하실려고요?

물론, 역으로 탐색한다고 한다면

1 1 1 1 1 1 1 ... 1 3 4 7 11 100222

이런 데이터에서 걸리겠죠.

힌트 하나 드릴게요.

1 3 4 5 6 7 11 12 14 16 17 ...

밑줄 친 부분을 먼저 주목해 주세요. 9보다 작게 되는 최초의 위치.

9보다 크게 되는 최초의 위치는 어떻게 찾을 수 있을지는 밑줄을 보시면 되고요.

이거 역시 이분 탐색으로 찾으실 수 있습니다.

yujjjang 6년 전 0

감사합니다. 덕분에 무엇이 문제점인지 알고 다시 고쳤습니다.

문제해결에 도움을 주셔서 너무 감사드립니다. !!

감기조심하세요~

chogahui05 6년 전 1

어려운 알고리즘 하나 하셨네요..

보통 이진탐색만 배우는데. 저도 여기서 이분탐색을 배웠어요.. 제일 쉽게 설명하자면

인접한 것끼리 비교하는 연산이 핵심이고요.

이것도 어려워지면 한없이 어려워지는 알고리즘이니.. 까다롭지요..

제가 못 푼 문제 중에서 2990번도 사실 정해가 이분 탐색입니다.

구현하기가 짜증날 정도라서 그냥 트라이를 써서 틀렸지만요.

함수 식만 잘 세우는 연습만 해 보세요.

추천 문제 하나만 링크하겠습니다.

https://www.acmicpc.net/proble...

yujjjang 6년 전 0

컴퓨터 공부를 시작한지 몇일이되지않아서.. 덕분에 좋은거 배워갑니다 !!

정답비율이 너무 낮아서 많이 두렵지만 오늘 한번 열심히 해보겠습니다.

너무 감사드립니다. 풀다가 모르는것 있으면 질문을 올릴거 같아서 .... 밤에 시간나시면 한번만 확인부탁드립니다 감사해요 !!

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

문제

문제

출처

ICPC

시간초과때문입니다.

yujjjang 6년 전 0

chogahui05 6년 전 1

yujjjang 6년 전 0

chogahui05 6년 전 1

yujjjang 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말