14889번

14889번 - 스타트와 링크

2017년 하반기 삼성전자 sw 역량테스트 문제이다.

나는 이때 직접 시험을 봤는데.. 그때 대충 팀 나누는 거 까지는 감 잡았는데 그 뒤로 멘붕이었는데..

다시 풀어보니 너무 쉬운 문제였다..

다만 처음에 팀을 두개로 안나누고, 한개의 팀으로 풀려다 보니 시간초과가 나는 부분이 있었다.

그 부분은 재귀함수에서 변수를 하나 추가해주는 방식으로 풀 수 있었다. 여기서 막혔었다.

팀을 두개로 나눠서 풀면, 복잡한 생각없이 풀 수 있는 문제였다.

<정답 코드 - 팀을 두개로 나눠서 >

#include<iostream>
#include<algorithm>
 
 
using namespace std;
int map1[21][21];
int n, ans = 987654321;
int HaveTeam[21];
 
void dfs(int num)
{
 
    if (num == n+1)
    {
        int ans1 = 0, ans2 = 0;
 
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (HaveTeam[i]==1 && HaveTeam[j]==1)
                {
                    ans1 += map1[i][j];
                }
                else if(HaveTeam[i]==2 && HaveTeam[j]==2)
                {
                    ans2 += map1[i][j];
                }
            }
        }
 
        ans = min(ans, abs(ans1 - ans2));
 
        return;
    }
 
    HaveTeam[num] = 1;
    dfs(num + 1);
 
    HaveTeam[num] = 2;
    dfs(num + 1);
}
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &map1[i][j]);
        }
    }
 
    dfs(1);
 
    printf("%d\n", ans);
    return 0;
}

<정답 코드 - 팀을 하나로 >

#include<iostream>
#include<algorithm>
 
 
using namespace std;
int map1[21][21];
int n, ans = 987654321;
bool HaveTeam[21];
 
void dfs(int num, int now)
{
    if (num>n/2)
    {
        return;
    }
 
    if (num == n / 2)
    {
        int ans1 = 0, ans2 = 0;
 
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (HaveTeam[i] && HaveTeam[j])
                {
                    ans1 += map1[i][j];
                }
                else if(!HaveTeam[i]&&!HaveTeam[j])
                {
                    ans2 += map1[i][j];
                }
            }
        }
 
        ans = min(ans, abs(ans1 - ans2));
 
        return;
    }
 
    for (int i = now+1; i <= n; i++)
    {
        if (!HaveTeam[i])
        {
            HaveTeam[i] = true;
            
            dfs(num + 1, i);
 
            HaveTeam[i] = false;
        }
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &map1[i][j]);
        }
    }
 
    dfs(0,0);
 
    printf("%d\n", ans);
    return 0;
}