글 읽기 - 39%에서 틀렸습니다가 나오는 이유를 모르겠습니다

wonjnlee 6년 전 0

혹시 제가 알지못하는 반례가 있을까요?

샘플 태스크는 모두 통과했습니다

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

int N;

int map[21][21];
int team[21];

long long int result = 100000000000;

long long int cal() {
    long long int team1_val = 0;
    long long int team2_val = 0;
    vector <int> team1;
    vector <int> team2;
    for(int i=0; i<N; i++) {
        if(team[i] == 1)    team1.push_back(i);
        else                team2.push_back(i);
    }
    for(int i=0; i<team1.size()-1; i++) {
        //for(int j=1; j<team1.size(); j++) { 이부분 문제
        for(int j=i+1; j<team1.size(); j++) {
            team1_val += (map[team1[i]][team1[j]] + map[team1[j]][team1[i]]);
            team2_val += (map[team2[i]][team2[j]] + map[team2[j]][team2[i]]);
        }
    }
    return abs(team2_val - team1_val);
}

void DFS(int index, int cnt) {
    if(index > N) return;
    if(cnt >= N/2) {
        result = min(result, cal());
        return;
    }
    //DFS(index + 1, cnt);
    team[index] = 1;
    DFS(index + 1, cnt + 1);
    team[index] = 0;
    DFS(index + 1, cnt);
}

int main(void)
{
    cin>>N;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) cin>>map[i][j];
    }
    DFS(1,0);
    cout<<result<<endl;
    return 0;
}

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

문제

문제

출처

ICPC

39%에서 틀렸습니다가 나오는 이유를 모르겠습니다

wonjnlee 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말