글 읽기 - C언어로 풀었습니다. 반례를 찾아줄 수 있나요..?

jujoun 3년 전 0

C언어로 풀었습니다..

full함수를 통해 백트래킹 과정을 수행했고 그 과정중에 N/2 조합을 stack1에 담았습니다.

그후 stack2_make를 통해 stack2를 만들고 score로 최소 result를 찾는 알고리즘입니다..

알고리즘 자체가 잘못 된거인지 코딩을 잘못한거인지 모르겟어서 질문합니다..

#include <stdio.h>
#include <stdlib.h>

int N;
int a[20][20];
int t_1;
int t_2;
int result = 100000000;
int stack[10];
int stack2[10];
int isused[20];
void stack2_make(){
    int q = 0;
    for(int i=0 ; i<N ;i++){
        if(isused[i]==0){
            stack2[q] = i+1;
            q++;
        }
    }
}
void score(){
    stack2_make();
    for(int i = 0; i<N/2 ; i++){
        for(int j = 0; j<N/2 ; j++){
        if(i == j) {continue;}
        t_1 += a[stack[i]-1][stack[j]-1];
        t_2 += a[stack2[i]-1][stack2[j]-1];
        }
    }
    if(result > abs(t_1-t_2)){result = abs(t_1-t_2);}
}
void full(int x){
    if( x == N/2){
        score();
        t_1 = 0;
        t_2 = 0;
    }
    for(int i = 0; i<N ; i++){
        if(isused[i] == 0 && (x==0||stack[x-1] <i+1)){
            stack[x] = i+1;
            isused[i] = 1;
            full(x+1);
            isused[i] = 0;
            stack[x] = 0;
        }
    }
}
int main(){
    scanf("%d" , &N);
    for(int i = 0;i<N ; i++){
        for(int j = 0; j<N ; j++){
            scanf("%d",&a[i][j]);
        }
    }
    full(0);
    printf("%d" , result);
}

jujoun 3년 전 1

if( x == N/2){

score();

t_1 = 0;

t_2 = 0;

}하고 return;으로 안끝내서 틀린거였습니다..ㅜㅜ

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

문제

문제

출처

ICPC

C언어로 풀었습니다. 반례를 찾아줄 수 있나요..?

jujoun 3년 전 0

jujoun 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말