글 읽기 - 한 줄만 봐주세요 ㅠㅠ

pastpot 3년 전 0

계속 틀리다가 처음부터 다른 방식으로 풀어서 결국에는 풀었는데요

틀렸던게 왜 틀렸는지 모르겠다가 49번째 줄

if(*real >= (fact(n)/(fact(n/2)*fact(n/2)))/2 ) return;

이것만 지우니까 틀렸다고 떴던게 맞았다고 하네요

그런데 제 생각에 저 문장이 왜 문제인지 모르겠어서요

조합알고리즘(?)에서 N개 중에서 N/2개를 뽑을 때 집합이 두개니까 한쪽 집합만 구하면 나머지는 자동으로 구해지니까

전체의 절반만 구하려고 저렇게 쓴건데 뭐가 문제죠 ㅠㅠ 디버깅(?)을계속 해봤는데도 모르겠어서요

프로그래밍 할때 쓰는 단어가 아직 많이 미숙하네요 알려주시면 감사하겠습니다

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
void comb(int n, int *s, int i, int cnt, int *real, int **arr, int *min);
int cal(int *s, int **arr, int n);
void myp(int n, int *a){
    for(int i=1; i<=n; i++)
        printf("%3d",a[i]);
    puts("");
    return ;
}
int fact(int n){
    int answer=1;
    for(int i=1; i<=n; i++)
        answer *= i;
    return answer;
}
int main(){
    int n;
    scanf("%d",&n);
    int **arr = (int **)malloc(sizeof(int*)*(n+1));
    for(int i=1; i <= n; i++)
        arr[i] = (int *)malloc(sizeof(int)*(n+1));
    int *s = (int *)calloc(n/2 + 1, sizeof(int));

    for(int i=1; i <= n; i++)
        for(int j=1; j <= n; j++)
            scanf("%d",&arr[i][j]);


    int *min = (int *)calloc(1,sizeof(int));
    int *real = (int *)calloc(1,sizeof(int));
    *min = INT_MAX;
    *real = 0;
    comb(n, s, 1, 1, real, arr, min);
    printf("%d", *min);


    for(int i=1; i<=n; i++)
        free(arr[i]);
    free(arr);
    free(s);
    free(min);
    free(real);
    return 0;
}

void comb(int n, int *s, int i, int cnt, int *real, int **arr, int *min){
    if(*real >= (fact(n)/(fact(n/2)*fact(n/2)))/2 ) return;
    if( cnt > n/2){
        return ;
    }
    if( i > n)
        return ;
    s[cnt] = i;
    if(cnt == n/2){
        *real += 1;
//      printf("real = %d\n", *real);
//      myp(cnt,s);
        int an = cal(s,arr,n);
        if( an < *min){
            *min = an;
//          printf("min = %d\n",*min);
        }
    }
    comb(n, s, i+1, cnt+1, real, arr, min);
    comb(n, s, i+1, cnt, real, arr, min);
    return ;
}

int cal(int *s, int **arr, int n){
    int answer=0;
    int exist=0;
    int k=1;
    int j;
    int *rev = (int*)malloc(sizeof(int)*n/2+1);
    for(int i=1; i<=n; i++){
        for(j=1; j<=n/2; j++){
            if(i == s[j])
                exist = 1;
        }
        if(exist == 0)
            rev[k++] = i;
        else
            exist = 0;
    }
    for(int i=1; i <= n/2; i++)
        for(int j=1; j <= n/2; j++){
            answer += arr[s[i]][s[j]];
            answer -= arr[rev[i]][rev[j]];
        }
    if(answer < 0) answer*=-1;
    free(rev);
    return answer;
}

jerrome2685 3년 전 1

N의 최댓값이 20인데, fact(20)을 호출하시면 정수 범위를 넘어가서 이상한 마이너스값을 리턴하게 됩니다.

즉, 멈추면 안 되는데 멈추게 되는 상황이 발생할 수 있습니다.

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

문제

문제

출처

ICPC

한 줄만 봐주세요 ㅠㅠ

pastpot 3년 전 0

jerrome2685 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말