제2회 대학생 프로그래밍 온라인대회 연습문제 B 테이블 정리

ProgrammingAlgorithm
Algorithm, Programming

문제

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
using namespace std;
int tables[4][4];    // 테이블 상태
int Move(int, int);
int main()
{
    int T;
    cin >> T;    // 테스트 케이스의 개수
    for(int i = 0; i < T; i++)
    {
        int sum = 0;
        for(int j = 0; j < 4; j++)
        {
            for(int k = 0; k < 4; k++)
            {
                cin >> tables[j][k];
                sum += tables[j][k];
            }
        }
        cout << sum - Move(0, 0) << endl;
    }
    return 0;
}
int Move(int col, int flag)
{
    if(col >= 4)
    {
        return 0;
    }
    int max = 0;
    for(int i = 0; i < 4; i++)
    {
        if(flag & (1 << i))
        {
            continue;
        }
        int val = tables[i][col] + Move(col + 1, flag | (1 << i));
        if(val > max)
        {
            max = val;
        }
    }
    return max;
}

코멘트

실수로 배열에 행과 열을 반대로 저장해 푸는데 오래걸렸다. 가장 적게 이동한 인원을 찾는것과 전체 인원에서 이동안한 인원을 제외한 인원이 같기에 후자로 구하였다. 재귀적으로 백트래킹을 수행하였다.

Share Comments