글 읽기 - 반례를 못 찾겠습니다 질문에 있는 반례들 거의 다 넣어봤는데 맞게 나옵니다

dongyun9501 1년 전 0

반례가 있을까요? 아니면 코드가 틀린걸까요??

# include <stdio.h>

# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )


int partition(int list[], int left, int right){
  int pivot, temp;
  int low, high;

  low = left;
  high = right + 1;
  pivot = list[left]; 
  do{
    
    do {
      low++; // low는 left+1 에서 시작
    } while (low<=right && list[low]<pivot);

    /* list[high]가 피벗보다 크면 계속 high를 감소 */
    do {
      high--; //high는 right 에서 시작
    } while (high>=left && list[high]>pivot);

    // 만약 low와 high가 교차하지 않았으면 list[low]를 list[high] 교환
    if(low<high){
      SWAP(list[low], list[high], temp);
    }
  } while (low<high);

  // low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]를 교환
  SWAP(list[left], list[high], temp);

  // 피벗의 위치인 high를 반환
  return high;
}

// 퀵 정렬
void quick_sort(int list[], int left, int right){

  /* 정렬할 범위가 2개 이상의 데이터이면(리스트의 크기가 0이나 1이 아니면) */
  if(left<right){
    // partition 함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 -분할(Divide)
    int q = partition(list, left, right); // q: 피벗의 위치

    // 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
    quick_sort(list, left, q-1); // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 -정복(Conquer)
    quick_sort(list, q+1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 -정복(Conquer)
  }

}


int main() {
    int n;
    scanf("%d",&n);
    int max_weight;
    int rope_weight[1000000];
    for(int i=0; i<n; i++)
      {
        scanf("%d",&rope_weight[i]);
      }
   quick_sort(rope_weight,0,n-1);
  max_weight=rope_weight[0]*n;
  if(rope_weight[n-1]>max_weight)
  {
    max_weight=rope_weight[n-1];
  }
  printf("%d\n",max_weight);
    return 0;
}

playsworld16 1년 전 0

1개 혹은 n개의 로프를 쓰는 경우를 제외한 다른 경우도 답이 될 수 있습니다.

예)
3

1 5 9

9 (9 한 개 사용)

10 (5, 9 두 개 사용)

3 (1, 5, 9 세 개 사용)

dongyun9501 1년 전 1

아 제가 간과한 부분이 있네요 감사합니다 고수님!!

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

문제

문제

출처

ICPC

반례를 못 찾겠습니다 질문에 있는 반례들 거의 다 넣어봤는데 맞게 나옵니다

dongyun9501 1년 전 0

playsworld16 1년 전 0

dongyun9501 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말