글 읽기 - 테스트 케이스 어디가 오류가 나는걸까요?

hananakajima 8년 전 0

전에도 한번 올린적있는데, 테스트 케이스를 만들어봐도 다 통과되는데 어떨때 오류가 뜨는지 잘 모르겠네요.

푼 방법은, 우선 정렬되어서 제자리 있는 짐들은 다 제거한뒤에, 정렬된 수열과 정렬 안된 수열을 비교해서, 최소한도로 정렬하려면, 중복되지 않게 정리해야되므로, 정렬사이클을 구한뒤, 각 사이클에서 제일 작은 숫자를 사이클 갯수만큼 더하는 방법 (예 : 3-1-2 순으로 있다면, (1-3,3-2),(1-2,2-3),(1-3,1-2)등 교환 방법이 가능한데 1을 2번써서 교환하는게 제일 작게됨) 으로 구했습니다.

#include <stdio.h>
#include <stdlib.h>
int cmp(const void *arg1, const void *arg2)
{
  return *(int *)arg1 > *(int *) arg2 ? 1 : *(int *)arg1 < *(int *)arg2 ? -1 : 0;
}


main(){
       int arr[1000],sol[1000],jim[1000],num[1000];
       int i,j,p,k,n,temp=0,total=0,odd=0,min,tt=0,cycle,count=0;
       scanf("%d",&n);
       for(i=0;i<n;i++){
       scanf("%d",&arr[i]);
       sol[i]=arr[i];
       }
       qsort(sol,n,sizeof(int),cmp);
       
       for(i=0;i<n;i++){
       if(arr[i]==sol[i])
         arr[i]=-1;
       }
       for(i=0;i<n;i++){
         if(arr[i]!=-1){
           jim[count]=arr[i];
           sol[count]=jim[count];
           count++;
         }
       }
        qsort(sol,count,sizeof(int),cmp);      
       
       
              
       for(i=0;i<count;i++){
         for(j=0;j<count;j++){
       if(jim[i]==sol[j]){
       num[i]=j;
       sol[j]=-1;
       break;
       }
       }
       }
       
       for(i=0;i<count;i++){
         odd=0;
         total=0;
         cycle=0;
         if(num[i]!=-1){
            p=i;
            min=jim[i];
            while(num[p]!=-1){
                   odd++;
                   temp=num[p];
                        total+=jim[temp];
                        if(jim[temp]<min)
                        min=jim[temp];
                   num[p]=-1;
                   p=temp;

            }
         total+=min*(odd-2);
         tt+=total;
         }
       }
       
                printf("%d",tt);
                system("pause");
                  }

kesakiyo 8년 전 3

코드는 안보고 솔루션만 봤는데

꼭 싸이클 내에 있는 수가지고만 정렬을 하는 경우가 최선인 것은 아니에요.

만약에 싸이클 내부의 수가 100 101 102 103 이런데

싸이클에 포함이 안되는 짐의 무게가 1이라면

1인 짐을 가지고 정렬을 시키는게 훨씬 이득이겠죠?

hananakajima 8년 전 1

헐.....생각을 못했네요 감사합니다 ㅜㅜ

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

문제

문제

출처

ICPC

테스트 케이스 어디가 오류가 나는걸까요?

hananakajima 8년 전 0

kesakiyo 8년 전 3

hananakajima 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말