Matrix Sum

출처 : https://projecteuler.net/problem=345
다음과 같은 행렬에서 행과 열이 모두 다른 5개의 숫자를 추출하여 더했을 때 최대값은 3315 ( = 863 + 383 + 343 + 959 + 767) 가 된다.
5개의 숫자는 서로 같은 행에 있어도 안되고 같은 열에 있어도 안된다.

7 53 183 439 863
497 383 563 79 973
287 63 343 169 583
627 343 773 959 943
767 473 103 699 303

첫행에서 863 두번째행애서

다음 15 x 15 행렬에서 15개의 숫자를 위와 같은 방법으로 추출하여 더했을 때의 최대값을 구하시오.


  7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601  95 973
445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
 34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615  77 281 613 459 205 380 274 302  35 805
Hungarian method

2016/02/15 23:11

상파

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

8개의 풀이가 있습니다.

먼저 처음 타겟 되는 숫자들의 인덱스를 랜덤으로 줍니다. 서로 다른 Row열을 잡고 타겟 인덱스를 스왑할 시 합이 더 커지는 경우 스왑을 진행합니다. 이것을 반복하며 더이상 스왑할 경우가 없을때가 1회입니다. 이것을 50회 돌려서 그중에서의 최대값을 찾았습니다. 10회만 돌려도 최대값이 70프로 이상은 나오긴하는데 좀더 확실하게 50으로 돌렸습니다. 행과 열이 많아 지면 많아질수록 최대값을 내려면 더 많은 룹을 돌려야 됩니다. Github에 올라와진 답들이랑 비교해보면 완전히 다른 방법인데, 그래도 이 풀이 나름대로의 장점이 있다고 생각해서 그대로 진행했습니다. 어떻게 보면 TSP 문제랑 여러모로 비슷한 알고리즘이 필요한것 같습니다.

Stopwatch sw = new Stopwatch();
sw.Start();

int[,] m = {{007,053,183,439,863,497,383,563,079,973,287,063,343,169,583},
            {627,343,773,959,943,767,473,103,699,303,957,703,583,639,913},
            {447,283,463,029,023,487,463,993,119,883,327,493,423,159,743},
            {217,623,003,399,853,407,103,983,089,463,290,516,212,462,350},
            {960,376,682,962,300,780,486,502,912,800,250,346,172,812,350},
            {870,456,192,162,593,473,915,045,989,873,823,965,425,329,803},
            {973,965,905,919,133,673,665,235,509,613,673,815,165,992,326},
            {322,148,972,962,286,255,941,541,265,323,925,281,601,095,973},
            {445,721,011,525,473,065,511,164,138,672,018,428,154,448,848},
            {414,456,310,312,798,104,566,520,302,248,694,976,430,392,198},
            {184,829,373,181,631,101,969,613,840,740,778,458,284,760,390},
            {821,461,843,513,017,901,711,993,293,157,274,094,192,156,574},
            {034,124,004,878,450,476,712,914,838,669,875,299,823,329,699},
            {815,559,813,459,522,788,168,586,966,232,308,833,251,631,107},
            {813,883,451,509,615,077,281,613,459,205,380,274,302,035,805}};

int ROWS    = m.GetLength(0);
int COLUMNS = m.GetLength(1);

int[] createRandom = new int[ROWS];
int[] cIndex = new int[ROWS];
for (int i = 0; i < ROWS; i++)
    createRandom[i] = i;

Random rnd = new Random();
int r1cIndex, r2cIndex, sum, maxSum = 0;

for (int c = 0; c < 50; c++)
{
    sum = 0;
    List<int> tempRandom = createRandom.ToList();
    for (int i = 0; i < ROWS; i++)
    {
        int rndIndex = rnd.Next(0, tempRandom.Count);
        cIndex[i] = tempRandom[rndIndex];
        tempRandom.RemoveAt(rndIndex);
    }

    while (true)
    {
        bool isChanged = false;
        for (int r1 = 0; r1 < ROWS - 1; r1++)
        {
            for (int r2 = r1 + 1; r2 < ROWS; r2++)
            {
                r1cIndex = cIndex[r1];
                r2cIndex = cIndex[r2];

                if (m[r1, r1cIndex] + m[r2, r2cIndex] <
                    m[r1, r2cIndex] + m[r2, r1cIndex])
                {
                    cIndex[r1] = r2cIndex;
                    cIndex[r2] = r1cIndex;
                    isChanged = true;
                }
            }
        }
        if (!isChanged) break;
    }

    for (int r = 0; r < ROWS; r++)
        sum += m[r, cIndex[r]];

    maxSum = sum > maxSum ? sum : maxSum;
}
sw.Stop();

Console.WriteLine(string.Format("Maximum Sum : {0}", maxSum));
Console.WriteLine(string.Format("Elapsed Time : {0}", sw.Elapsed));

결과

Maximum Sum : 13938
Elapsed Time : 00:00:00.0003346
계속하려면 아무 키나 누르십시오 . . .
고생많으셨습니다 ^^ - 상파, 2016/02/20 20:12 M D
코드가 훌륭합니다. 많이 배웁니다. - 강 경수, 2016/07/11 15:18 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

쉬운 이해를 위해서 3x3 행렬을 예를 들어 설명해보겠습니다.
0행 - 1 2 3
1행 - 4 5 6
2행 - 7 8 9
일단 2행은 나중에 생각하고, 0행과 1행에서만 생각해봅시다. 0행과 1행에서 선택할 수 있는 열의 조합은 모두 3가지 입니다. 0과 1열, 0과 2열, 1과 2열입니다. 0과 1열이라 함은, 0행과 1행에서 0행은 0열, 1행은 1열을 고르던지 아니면 반대로 0행에서는 1열, 1행에서는 0열을 선택한다는 말입니다. 2가지경우중 최대값을 골라서 적당한 이름을 붙여서 저장합니다. 0과 1열일 경우 최대값은 6입니다. 0과 2열일 경우 최대값은 7입니다. 1과 2열일 경우 최대값은 8입니다.

2행에서 7(0열)을 선택할 경우, 0행,1행에서 두수를 골랐을 때(1과 2열)의 최대값은 8이 됩니다. 이경우 합은 15입니다.
2행에서 8(1열)을 선택할 경우 0,1행에서(0과 2열) 7이 됩니다. 합은 15입니다.
3행에서 9(2열)를 선택할 경우 0,1행에서(0과 1열) 6이 됩니다. 합은 15입니다.
아무렇게나 만든 예라서 최대값이 모두 15가 나오는군요. 어찌 되었든, 이런 방법을 확장해서 풀었습니다.

순열이 아니고 조합이라서 경우의 수가 생각보다 많진 않습니다. (몇천가지 정도)

#-*- coding: utf-8 -*-
#https://projecteuler.net/thread=345;page=8
from itertools import *
s='''\
  7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 9t41 541 265 323 925 281 601  95 973
445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
 34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615  77 281 613 459 205 380 274 302  35 805'''
s=[map(int,x.split()) for x in s.split('\n')]

'''
d[{0}]=7, d[{1}]=53, d[{2}]=183....
d[{0,1}]=max(d[{0}]+s[1][1],d[{0}]+s[1][1])
d[{0,2}]=max(d[{0}]+s[1][2],d[{2}]+s[1][0])
...
d[{0,1,2}] = max(d[{0,1}]+s[2][2], d[{0,2}]]+s[2][1], d[{1,2}]+s[2][0])
...
...

d[{a,b,c,d}] 의 의미는,
4행까지만 (a,b,c,d가 4개이므로) 생각했을때 a열,b열,c열,d열에서 각각 숫자 한개씩을
뽑아서 더했을 때의 최대값을 의미한다.
d[{a,b,c,d}] = max(d[{a,b,c}]+s[3][d], d[{a,b,d}]+s[3][c], d[({a,c,d})]+s[3][b], d[{b,c,d}]+s[3][a])
가 된다.
'''
d={frozenset([]):0}
l=len(s)
for i in range(l):
    for c in combinations(range(l),i+1):
        d[frozenset(c)]=max([d[frozenset(c)-{x}] + s[i][x] for x in frozenset(c)])

print d[frozenset(range(l))]

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
from itertools import *

nums = '''7 53 183 439 863 497 383 563 79 973 287 63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463 29 23 487 463 993 119 883 327 493 423 159 743
217 623 3 399 853 407 103 983 89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915 45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601 95 973
445 721 11 525 473 65 511 164 138 672 18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513 17 901 711 993 293 157 274 94 192 156 574
34 124 4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615 77 281 613 459 205 380 274 302 35 805'''

def cal(l):
    if len(l)>2:
        temp = []
        tlist = []
        c1 = combinations((x for x in range(len(l))), len(l)-1)
        while 1:
            try:x = c1.__next__()
            except:break
            c2 = combinations((x for x in range(len(l))), len(l)-1)
            while 1:
                temp = []
                try:y = c2.__next__()
                except:break
                for m in x:
                    temp.append(list((l[m][n] for n in y)))
                tempCal = cal(temp)
                xD = list(set(x for x in range(len(l))) - set(x))[0]
                yD = list(set(x for x in range(len(l))) - set(y))[0]
                tempCal += l[xD][yD]
                tlist.append(tempCal)
        return max(tlist)

    if len(l) == 2:
        return max(l[0][0]+l[1][1], l[1][0]+l[0][1])

if __name__ == '__main__':
    li = nums.split('\n')
    li = list(li[i].split() for i in range(len(li)))
    for x in range(len(li)):
        for y in range(len(li[x])): li[x][y] = int(li[x][y])
    cal(li)

재귀호출을 썼습니다. 상파님과 기본 원리는 같습니다. 33, 44, 7*7은 확인해봤습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C++ 입니다. 재귀로 해결했어요. 정답인 13938을 출력합니다.

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
#include <cmath> 
#include <string> 
#include <sstream> 
#include <vector> 
using namespace std;

string input = "7  53 183 439 863 497 383 563  79 973 287  63 343 169 583 627 343 773 959 943 767 473 103 699 303 957 703 583 639 913 447 283 463  29  23 487 463 993 119 883 327 493 423 159 743 217 623   3 399 853 407 103 983  89 463 290 516 212 462 350 960 376 682 962 300 780 486 502 912 800 250 346 172 812 350 870 456 192 162 593 473 915  45 989 873 823 965 425 329 803 973 965 905 919 133 673 665 235 509 613 673 815 165 992 326 322 148 972 962 286 255 941 541 265 323 925 281 601  95 973 445 721  11 525 473  65 511 164 138 672  18 428 154 448 848 414 456 310 312 798 104 566 520 302 248 694 976 430 392 198 184 829 373 181 631 101 969 613 840 740 778 458 284 760 390 821 461 843 513  17 901 711 993 293 157 274  94 192 156 574 34 124 4 878 450 476 712 914 838 669 875 299 823 329 699 815 559 813 459 522 788 168 586 966 232 308 833 251 631 107 813 883 451 509 615 77 281 613 459 205 380 274 302 35 805"; 

int grid[15][15]; //  배열
int chooseRow[15];  // 각 행에서 가장 큰 수를 고른다. 
bool used[15];  // 그 행을 이용했는지 판별 
int maxval;  

int toInt(string s){ // string 객체에 있는 수를 배열에 담기 위해서 만듬 
    int n; 
    istringstream iss (s); 
    iss >> n; 
    return n; 
}

bool chk(int row,int sum){
    for (int i = row; i < 15; i++){
        sum += chooseRow[i]; 
    }
    return (sum > maxval ? true : false);  
}


void recur(int n,int sum){
    if (n == 15){
        maxval = max(maxval,sum); 
        return; 
    }
    if (!chk(n,sum)) return;  
    for (int i = 0; i < 15; i++){
        if (used[i]) continue; 
        else{
            used[i] = true; 
            recur(n+1,sum+grid[n][i]);  
            used[i] = false; 
        }
    }
}

int main(){
    // 우선 grid를 string 객체로 받은뒤에 int grid로 옮깁니다.  
    istringstream iss (input);  
    string word; 
    int i = 0,j = 0;  
    while (iss >> word){
        grid[i][j++] = toInt(word);
        if (j > 14){
            i++; 
            j = 0; 
        }
        if (j == 15){
            break; 
        } 
    }
    for (int i = 0; i < 15; i++){
        for (int j = 0; j < 15; j++){
            chooseRow[i] = max(chooseRow[i],grid[i][j]); 
        }
    }
    recur(0,0); 
    cout << maxval << endl; 
    return 0;  
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

위 예시를 보면 일단 제일 큰 숫자 959는 같은 행, 열에서 더 큰 수가 없잖아요 그래서 일단 그거 찍고 다른 행에서 그 행에서 제일 큰 수를 고르는거죠 그 다음 유사한 원리로 반복한 후 각 경우의 수를 더해본 다음에 다른 행에도 똑같이 적용시키면 안될가요? 이때 경우의 수가 너무 많아지는 것을 방지하기 위해 처음 선택하는 '큰 수'는 범위를 지정하고 그 다음 '큰 수'를 선택함으로써 다른 행으로 옮겨진 작은 수의 하락하는 정도가 더 크면 안되니깐 경우의 수를 더해보면서 '안 될 것'들은 제외시키는거죠

풀이에 대한 생각같은 이런종류의 글은 문제에 댓글로 달아주시는게 좋을 것 같습니다. - 길가의풀, 2016/07/11 09:24 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.stream.IntStream;

import static java.lang.System.out;

public class MatrixSum {

    private static int len = 15;
    private static int max = 0;
    private static int[][] matrix = new int[len][len];

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new File(MatrixSum.class.getResource("").getPath() + "MatrixSum.txt"));
        IntStream.range(0, len).forEach(i -> IntStream.range(0, len).forEach(j -> matrix[i][j] = sc.nextInt()));
        perm(0, len, IntStream.range(0, len).toArray());
        out.println(max);
    }

    private static void perm(int s, int n, int[] arr) {
        if (n == s) {
            max(arr);
            return;
        }

        for (int i = s; i < n; i++) {
            if (i != s) swap(i, s, arr);
            perm(s + 1, n, arr);
            if (i != s) swap(i, s, arr);
        }
    }

    private static void swap(int i, int s, int[] arr) {
        int temp = arr[i];
        arr[i] = arr[s];
        arr[s] = temp;
    }

    private static void max(int[] arr) {
        int t = 0;
        for (int i = 0; i < len; i++) {
            t = t + matrix[i][arr[i]];
        }
        if (t > max) {
            out.println(max);
            max = t;
        }
    }
}

답이 나오긴했는데 너무 느리네요.. -_-;;

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python3

각 행에서 숫자를 하나씩 선택하고, 선택한 숫자가 있는 열을 제외한다고 생각하면

1행 N열 중에서 하나, 2행 N-1열 중에서 하나, 3행 N-2열 중에서 하나, ... 이므로 경우의 수는 N!입니다.

모든 경우 탐색:

def maxsum(i = 0, cols = set()):  # i행에서 하나를 택한 경우를 탐색한다. cols는 제외할 열 번호들
    if i == N:
        return 0

    M = 0
    for j in set(range(N)) - cols:
        M = max(M, arr[i][j] + maxsum(i + 1, cols | {j}))

    return M

입력처리:

inp1 = \
'''7 53 183 439 863
 497 383 563 79 973
 287 63 343 169 583
 627 343 773 959 943
767 473 103 699 303'''

def str_to_arr(s):
    arr = []
    for row in s.split('\n'):
        arr.append(list(map(int, row.split())))

    return arr, len(arr)

arr, N = str_to_arr(inp1)
print(maxsum())

.

가지치기:

def maxsum(i = 0, lsum = 0, cols = set()):  # i행에서 선택. lsum = i-1행까지 합, cols = 제외할 열 번호
    global gsum
    if i == N:
        gsum = max(gsum, lsum)

    raw = []
    for j in set(range(N)) - cols:
        raw.append((arr[i][j], j))
    raw.sort(key = lambda x: x[0], reverse = True)

    for x in raw:
        upperbound = lsum + x[0] + sum(rawmax[i+1:])
        if upperbound > gsum:
            maxsum(i + 1, lsum + x[0], cols | {x[1]})


arr, N = str_to_arr(inp2)
rawmax = [max(row) for row in arr]
gsum = 0
maxsum()
print(gsum) # 13938, 0.49 sec

O(N!)은 알고리즘이라고 하기 부끄럽죠. 가지치기를 좀 했습니다. 두 가지를 추가했는데..

바뀐 코드에서 전역 변수 gsum은 현재까지 가장 좋은 답이고, rawmax는 각 행의 가장 큰 값들입니다.

첫 번쨰 입력을 예로 들면 rawmax = [863, 973, 583, 959, 767] 이 됩니다.

.

  1. upperbound

현재 상태가 i-1행까지 선택했고 선택한 숫자들을 더한 값이 lsum이라면,

이 상태에서 탐색한 답은 어떤 경우에도 lsum + sum(i번 행부터 마지막 행까지 각 행의 최대값들) 을 넘을 수 없습니다(upperbound)

따라서 upperbound가 gsum보다 작거나 같으면 더 깊이 탐색할 필요가 없어집니다. (위 코드에서는 깊이를 하나 줄여보려고 약간 다르게 썼습니다)

예를 들어 첫 번째 입력 예에서 gsum이 3315로 최적해를 이미 구한 상태이고,

0~4행 중, 0, 1, 2 행에서 각각 863, 383, 169 를 선택했고(lsum = 1415) 3 행에서 선택할 차례라고 합시다.

그럼 남은 3행, 4행에서 각 행의 최대값은 959, 767인데 lsum에 이 둘을 더하면

1415 + 959 + 767 = 3141

즉 이 상태에서 앞으로 어떤 선택을 하더라도 3141을 넘을 수 없고, 현재까지 최적해가 3315 이므로 더 좋은 해를 구할 가능성이 없습니다.

.

  1. 큰 수부터 선택

초반에 좋은 해를 구할수록 가지치기를 많이 할 수 있으므로, 각 행에서 왼쪽-->오른쪽으로 탐색하지 않고 숫자가 큰 순서대로 선택해서 탐색합니다.

첫 번째 입력에서 두 번째 행을 예로 들면,

[497, 383, 563, 79, 973]를 정렬하면 [973, 563, 497, 383, 79] 이고,

열 번호를 기억해야 하므로 raw = [(973,4), (563,2), (497,0), (383,1), (79,3)] 이 됩니다.

이렇게 raw를 만든 후 큰 숫자부터 탐색합니다.

혹은 이렇게 하지 않고, 앞에 다른 분이 하신 것처럼 random이나 greedy로 적당히 좋은 해를 구해놓고 시작하는 방법도 좋습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
  1. 파이썬 3.6입니다.
  2. 재귀를 사용했습니다.
  3. 낮은차원의 행렬에서는 성립되는걸 확인했지만 15x15는 안녕...
def mxsum(matrix):
    import numpy as np
    arr = np.array(matrix)

    if arr.shape != (1,1):
        hub = [] #여기에 모든 값들을 저장하고 최댓값을 뽑아냄 
        for i in range(len(list(arr[0]))):
            for j in range(len(list(arr[:,0]))):
                hub.append(arr[i][j] + mxsum(np.concatenate(\
                   (np.concatenate((arr[:i,:j],arr[i+1:,:j])),\
                   np.concatenate((arr[:i,j+1:],arr[i+1:,j+1:])))
                   ,-1))) #(i,j)값을 제외한 행렬을 만드는 과정
        return max(hub)
    else:
        return max(max(arr)) #arr가 2차원이어서 max도 2개


mx = [[7,  53, 183, 439, 863, 497, 383, 563,  79, 973, 287,  63, 343, 169, 583],
[627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913],
[447, 283, 463,  29,  23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743],
[217, 623,   3, 399, 853, 407, 103, 983,  89, 463, 290, 516, 212, 462, 350],
[960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350],
[870, 456, 192, 162, 593, 473, 915,  45, 989, 873, 823, 965, 425, 329, 803],
[973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326],
[322, 148, 972, 962, 286, 255, 941, 541, 265, 323, 925, 281, 601,  95, 973],
[445, 721,  11, 525, 473,  65, 511, 164, 138, 672,  18, 428, 154, 448, 848],
[414, 456, 310, 312, 798, 104, 566, 520, 302, 248, 694, 976, 430, 392, 198],
[184, 829, 373, 181, 631, 101, 969, 613, 840, 740, 778, 458, 284, 760, 390],
[821, 461, 843, 513,  17, 901, 711, 993, 293, 157, 274,  94, 192, 156, 574],
[ 34, 124,   4, 878, 450, 476, 712, 914, 838, 669, 875, 299, 823, 329, 699],
[815, 559, 813, 459, 522, 788, 168, 586, 966, 232, 308, 833, 251, 631, 107],
[813, 883, 451, 509, 615,  77, 281, 613, 459, 205, 380, 274, 302,  35, 805]]      

#mxsum(mx)
제머리로는 복잡도를 더 낮게 만들수 없을것같아서 일단 답을 제출하였습니다. - 고든, 2017/08/22 15:39 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

Hungarian method x 1

언어별 풀이 현황
전 체 x 8
cs x 1
python x 4
cpp x 1
기 타 x 1
java x 1