Gidhub BE Developer

SW Expert Academy - 요리사

2018-05-11
goodGid

Problem

Problem URL : 요리사


[1] Answer Code (18. 08. 27)

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int n,ans;
int map[21][21];
int chk[21];

void dfs(int idx,int size){
    if(size == n / 2 ){
        int temp1 = 0 , temp2 = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if( chk[i] && chk[j])
                    temp1 += map[i][j];
                else if ( !chk[i] && !chk[j])
                    temp2 += map[i][j];
            } // end of for j
        } // end of for i
        ans = ans > abs(temp1 - temp2) ? abs(temp1 - temp2) : ans;
    } // end of if
    else{
        for(int i=idx; i<=n; i++){
            chk[i] = 1;
            dfs(i+1, size+1);
            chk[i] = 0;
        }
    } // end of else
}
int main(){
    int TC;
    cin >> TC;
    for (int tc=1; tc<=TC; tc++) {
        cin >> n;
        ans = 2e9;
        memset(map,0,sizeof(map));
        memset(chk,0,sizeof(chk));
        
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",&map[i][j]);
        dfs(1,0);
        
        printf("#%d %d\n",tc, ans);
    } // end of for tc
    
    return 0;
}

Review

  • 무난하게 풀었다. 그런데 집중해서 안풀어서 시간은 정확히 측정 못했다.

  • 시간복잡도 계산은 어떻게 해야하는지 모르겠네…

  • 이번 코드는 223ms 걸렸고 기존 코드는 554ms 시간은 확실히 줄었다.


[2] Answer Code (18. 05. 11)


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

int map[16][16];
int visit[16];
int ans,n;

int dfs(int idx, int cnt){
    if( cnt == n>>1){
        vector<int> v[2];
        for(int i=0; i<n; i++){
            if(visit[i]) v[1].push_back(i); else v[0].push_back(i);
        } // for i Loop
        
        int sum1, sum2;
        sum1 = sum2 = 0;
        
        for (int i = 0; i < n/2; i++) {
            for (int j = 0; j < n/2; j++) {
                if (i == j)continue;
                sum1 += map[v[0][i]][v[0][j]];
                sum2 += map[v[1][i]][v[1][j]];
            }
        }
        
        sum1 = abs(sum1-sum2);
        return sum1 > ans ? ans : sum1;
    }
    for(int i=idx; i<n; i++){
        visit[i] = 1 ;
        ans = min(ans, dfs(i+1,cnt+1));
        visit[i] = 0 ;
    }
    return ans;
}


int main(){
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        memset(visit,0,sizeof(visit));
        ans = 2e9;
        
        cin >> n;
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&map[i][j]);
        
        ans = min(dfs(0,0),ans);

        printf("#%d %d\n",tc,ans);
    }
    return 0;
}

Review

  • 1시간 걸림

  • 차이값을 계산하는 부분에서 nPr인데 nCr로 생각했다.

// Before
    for(int i=0; i<(n >> 1) -1; i++){
        sum1 += map[ v[0][i] ][ v[0][i+1] ] + map[ v[0][i+1] ][ v[0][i] ];
        sum2 += map[ v[1][i] ][ v[1][i+1] ] + map[ v[1][i+1] ][ v[1][i] ];
    }


 // After
    for (int i = 0; i < n/2; i++) {
        for (int j = 0; j < n/2; j++) {
            if (i == j)continue;
            sum1 += map[v[0][i]][v[0][j]];
            sum2 += map[v[1][i]][v[1][j]];
        }
    }

  • 알고리즘 + 구현까지 40분정도 걸렸는데 계산 로직때문에 시간이 많이 걸렸다.

  • 정답 코드를 보고 나의 틀린 부분을 캐치

  • 다음부터는 저런 실수하지 말자 !

  • 다른 정답코드보다 실행시간이 좀 걸린다. 이유가 뭘까?


Comments

Content