문제 설명

말하는 문을 지난 일행은 왕좌의 대청으로 오르는 마지막 계단 앞에 섰습니다. 계단 위에는 사자 왕이 건 흑마법 봉인이 겹겹이 걸려 있었습니다.
그때 라이캣의 품에서 피스 스톤이 빛나기 시작했습니다. 개리의 스페이스 스톤, 자바독의 마인드 스톤, 빙키의 리얼리티 스톤, 뮤라의 타임 스톤, 소울곰의 소울 스톤, 대리인 No.1의 파워 스톤도 차례로 빛을 냈습니다. 오랜만에 한자리에 모인 7원석이 서로 공명하며, 그 빛은 함께 온 비밀조직 '호두'의 일원과 부족 친구들에게까지 번져 나갔습니다.
"봉인 하나에 한 명씩 맡는다냥! 누가 어느 봉인을 맡느냐에 따라 공명의 세기가 다르다냥."
"그렇다고 가장 센 자리부터 먼저 차지하면 안 된다 개굴. 전체 합을 따져야 한다 개굴!"
봉인은 m개, 동료도 m명입니다. data[i][j]는 i번 동료가 j번 봉인을 맡았을 때 생기는 공명의 세기입니다(번호는 0부터 셉니다). 동료마다 서로 다른 봉인을 하나씩 맡아, 모든 봉인에 동료가 정확히 한 명씩 서도록 할 때 공명 세기 합의 최댓값을 return 하세요.
제한 사항
- m은 1 이상 16 이하입니다.
data는 m×m 크기의 2차원 리스트이고, 모든 값은 0 이상 1,000 이하의 정수입니다.- m이 16이면 동료를 봉인에 배정하는 방법이 약 20조 가지(16!)라, 모든 배정을 하나씩 따지면 시간 안에 끝나지 않습니다.
입출력 예
| 입력 | 출력 |
|---|---|
| [[10, 9, 1], [9, 1, 1], [1, 8, 2]] | 20 |
| [[30, 12, 45, 7], [28, 40, 9, 33], [50, 22, 18, 26], [15, 37, 41, 20]] | 165 |
| [[62, 15, 88, 40, 73, 25, 51], [47, 90, 33, 12, 68, 55, 20], [81, 36, 54, 77, 9, 63, 42], [18, 70, 29, 95, 44, 31, 86], [59, 24, 66, 38, 92, 17, 75], [35, 83, 11, 60, 27, 99, 48], [74, 41, 93, 22, 56, 30, 65]] | 610 |
입출력 설명
입출력 예 #1
| 0번 봉인 | 1번 봉인 | 2번 봉인 | |
|---|---|---|---|
| 0번 동료 | 10 | 9 | 1 |
| 1번 동료 | 9 | 1 | 1 |
| 2번 동료 | 1 | 8 | 2 |
가장 센 10(0번 동료가 0번 봉인)부터 고르면, 남은 두 동료로 만들 수 있는 합은 많아야 1 + 8 = 9라서 모두 19입니다. 0번 동료가 1번 봉인(9), 1번 동료가 0번 봉인(9), 2번 동료가 2번 봉인(2)을 맡으면 20으로 가장 큽니다.
입출력 예 #2
0번 동료가 2번 봉인(45), 1번 동료가 3번 봉인(33), 2번 동료가 0번 봉인(50), 3번 동료가 1번 봉인(37)을 맡으면 45 + 33 + 50 + 37 = 165로 가장 큽니다.
입출력 예 #3
원석을 가진 일곱 동료만 봉인 일곱 개를 맡는 경우입니다. 0번~6번 동료가 차례로 2, 1, 0, 3, 4, 5, 6번 봉인을 맡으면 88 + 90 + 81 + 95 + 92 + 99 + 65 = 610으로 가장 큽니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | [[10, 9, 1], [9, 1, 1], [1, 8, 2]] | 20 |
| 2 | [[30, 12, 45, 7], [28, 40, 9, 33], [50, 22, 18, 26], [15, 37, 41, 20]] | 165 |
| 3 | [[62, 15, 88, 40, 73, 25, 51], [47, 90, 33, 12, 68, 55, 20], [81, 36, 54, 77, 9, 63, 42], [18, 70, 29, 95, 44, 31, 86], [59, 24, 66, 38, 92, 17, 75], [35, 83, 11, 60, 27, 99, 48], [74, 41, 93, 22, 56, 30, 65]] | 610 |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 15개도 함께 채점해요.