글 읽기 - pruning 안하면 맞는데 하면 59%에서 틀립니다.. 왜 그럴까요?

suno 3년 전 0

안녕하세요.

이 문제를 backtraking search로 풀었습니다.

그런데 효율을 위해서 점수 차이<0일 때는 탐색하지 않도록 했는데요.

n = 4이면, 팀1 팀2가 1,2 / 3,4 인 것과 3,4 / 1,2인 것이 같은 상황이라, 점수차가 양수 혹은 0인 한쪽만 탐색하면 된다고 생각했습니다.

그래서 if (diff < 0) return INF;를 넣었는데요. 이것을 넣은 버전(https://www.acmicpc.net/source...)은 59%에서 '틀렸습니다'가 뜨고 넣지 않은 버전(https://www.acmicpc.net/source...)은 '맞았습니다!!'가 뜹니다.

이렇게 가지치기하면 안 되는 이유가 있을까요? diff = 0인 경우도 탐색하니 문제가 없다고 생각했는데 왜 틀리는지 모르겠습니다.

저 혼자 생각해봐도 도저히 이유를 알 수 없어 도움을 청합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <assert.h>
#include <string.h>
#include <string>

#define MAX 22
#define INF 987654321

using namespace std;

/* 문제 정의
nxn 행렬 -> Sij합 차이의 최솟값
n<=20
 */

/* 해결 알고리즘 생각
모든 조합 확인 nCn/2 = O(n^5)?으로 해결 가능

전처리
Tij = Sij + Sji
i  1 2 3 4  sum
---------------
1  0 5 9 6  20
2  5 0 6 10 21
3  9 6 0 7  22
4  6 107 0  23

*/

int s[MAX][MAX] = {
    0,
};
int sum[MAX] = {
    0,
};
int permu_team1[MAX];
int n, diff = 0;

int findMinDiff(int index, int lower_bound)
{
    // if (diff < 0)
    //     return INF; 문제의 부분

    if (index == n / 2)
    {
        return abs(diff);
    }
    assert(index < n / 2);

    int minDiff = INF;
    for (int i = lower_bound; i <= n; i++)
    {
        diff -= sum[i];
        minDiff = min(minDiff, findMinDiff(index + 1, i + 1));
        diff += sum[i];
    }
    return minDiff;
}

int main()
{
    ////////////////////input////////////////////
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> n;
    int temp;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> temp;
            s[i][j] += temp;
            s[j][i] += temp;
            diff += temp;
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum[i] += s[i][j];

    ///////////////////solution//////////////////
    int result = findMinDiff(0, 1);

    ////////////////////output///////////////////
    cout << result;

    return 0;
}

/*legacy



*/

djm03178 3년 전 1

인덱스를 전체적으로 0~n-1로 사용하셨는데 findMinDiff 함수에서만 1~n으로 사용하신 것 같습니다. 그래서 최적이 되는 답이면서 diff가 음이 아닌 정수로 유지되게 하려면 0번을 뽑아야 하는 경우에 틀리게 됩니다. 시작을 0번부터 하고, 53번째 줄도 i < n으로 돌리면 맞습니다.

suno 3년 전 0

정말이네요. 감사합니다!!!

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

문제

문제

출처

ICPC

pruning 안하면 맞는데 하면 59%에서 틀립니다.. 왜 그럴까요?

suno 3년 전 0

djm03178 3년 전 1

suno 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말