문제 링크 (opens new window)

문제

1. 조합을 통해 완전탐색하는 문제
2. 사전 순이라는 정의에 따라 원소 갯수와 상관없이 [3]보다 [1,2,3]이 앞선다는 것을 명심해야됨
3. for문의 i 변수는 N개 중 선택된 i개를 의미한다.
4. for문의 j 변수를 통해 선택된 i의 이진데이터 1비트값을 기준으로 input을 인덱싱한다.

import Foundation

let N = Int(readLine()!)!
var input: [[Int]] = .init(repeating: .init(repeating: 0, count: 5), count: N)
var minimum: [Int] = readLine()!.split(separator: " ").map { Int($0)! }
var value = Int.max
var retValue: [Int:[[Int]]] = [:]

for i in 0..<N {
    input[i] = readLine()!.split(separator: " ").map { Int($0)! }
}

for i in 1..<1<<N {
    var nutrientSum = [0, 0, 0, 0]
    var money = 0
    var indicies: [Int] = []

    // 고르기
    for j in 0..<N {
        if i & (1 << j) != 0 {
            nutrientSum[0] += input[j][0]
            nutrientSum[1] += input[j][1]
            nutrientSum[2] += input[j][2]
            nutrientSum [3] += input[j][3]
            money += input[j][4]
            indicies.append(j)
        }
    }

    if nutrientSum[0] >= minimum[0]
        && nutrientSum[1] >= minimum[1]
        && nutrientSum[2] >= minimum[2]
        && nutrientSum[3] >= minimum[3] {
        if value >= money {
            value = money
            if let _ = retValue[value] {
                retValue[value]!.append(indicies)
            } else {
                retValue[value] = [indicies]
            }
        }
    }
}
if value == Int.max {
    print(-1)
    exit(0)
}
print(value)
retValue[value]!.sorted(by: { prev, next in
    return prev.map { String($0) }.joined() < next.map { String($0) }.joined()
})[0]
    .forEach({
        print($0 + 1, terminator: " ")
    })