백준, BOJ, 14889번 C++ [CPP]

그렇게 어렵진 않은 백트래킹 문제였다.

역시나 초기화 하지 않아서 틀린...아주 기초적인 문제다.

 

시간도 아주 여유로운 문제였다.

https://www.acmicpc.net/problem/14889

 

 

---

 

#맞는 풀이

#include<iostream>
#include<vector>
#include<cstdlib> // 절댓값

using namespace std;

int N;
int num[21][21]; // 최대 20명의 상대점수를 넣어놓음. (1~20만 씀 0 안씀)
int m = 10000; //최솟값 (임의로 크게 잡아놓음)
bool check[21]; // 팀원으로 뽑혔는지 확인해야함 (1~20만 쓸거임 0 안씀)

vector<int> target; // 뽑은팀 (숫자)

void func(int cnt) {
    //절반을 뽑았을 때
    //10몀 뽑은 팀과 남은 팀의 차이를 구분해야함.
    if (cnt == N / 2) {
        vector<int> leftteam; // 남은팀 (숫자) -> 초기화 안하는 실수함(전역선언함..ㅠ)
        //남은 팀(숫자 확인)
        for (int i = 1; i <= N; i++) {
            if (check[i] == false) {
                leftteam.push_back(i);
            }
        }

        //뽑힌팀 점수 합
        int tgscore = 0;
        for (int a : target) {
            for (int b : target) {
                tgscore += num[a][b];
            }
        }
        //남은팀 점수 합
        int lfscore = 0;
        for (int a : leftteam) {
            for (int b : leftteam) {
                lfscore += num[a][b];
            }
        }
        int diff = abs(lfscore - tgscore); // 절댓값으로 차이만 꺼냄
        if (m >= diff) {
            m = diff;
        }
        return;
    }

    for (int i = 1; i <= N; i++) {
        //선택
        if (check[i])continue; // 사용됐으면(true) 다른 번호로 넘어감.
        if (!target.empty()&&target.back() > i) continue; // 어차피 앞에서 이미 선택했음 처음 들어갈 때 예외
        //(순서가 존재하지 않으므로 1이면 2를 이미 선택해봤고 그러므로 2는 굳이 1을 선택하지 않음)
        target.push_back(i); // 해당번호 추가
        check[i] = true;

        //구현
        func(cnt + 1);

        //복원
        target.pop_back();
        check[i] = false;

    }
}
int main() {

    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> num[i][j];
        }
    }
    func(0);
    cout << m;
}

 

여기서 시간을 줄인 핵심은

굳이 자기보다 작은 숫자는 고르지 않아도 된다는 것이었다.

팀은 순서가 없기 때문에 permutation이 아니라 combination이었다.

그리고 행과 열이 같으면 값이 0인 것을 이용해서 중복되어도

값이 변하지 않아서 계산하기 쉽다는 것을 이용했다.