Gidhub BE Developer

[BOJ] 14889. 스타트와 링크

2018-10-17
goodGid

Problem

Problem URL : 스타트와 링크


[1] Answer Code (18. 10. 17)

#include<iostream>
#include<vector>
#define p pair<int,int>
using namespace std;

int map[20][20];
int pick[20];

int n;
int ans;

void dfs(int idx, int p_cnt){
    if(p_cnt == n/2){
        int sum1 = 0;
        int sum2 = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(pick[i] == pick[j] && pick[i] == 1)
                    sum1 += map[i][j];
                if(pick[i] == pick[j] && pick[i] == 0)
                    sum2 += map[i][j];
            }
        }
        ans = ans < abs(sum1 - sum2) ? ans : abs(sum1 - sum2);
        return ;
    }
    
    for(int i=idx; i<n; i++){
        pick[i] = 1;
        dfs(i+1, p_cnt + 1);
        pick[i] = 0;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ans = 2e9;
    cin >> n;
    
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> map[i][j];
    
    dfs(0,0);
    
    cout << ans << endl;
    return 0;
}

Review

  • 삼성 역량 테스트 기출 문제

  • 단순 DFS


Comments

Content