[백준 2798] 블랙잭 (Swift)

2798번: 블랙잭

• 합이 주어진 숫자를 넘지 않으면서 최대한 가까운 숫자 3개의 조합을 구해 그 합을 출력하는 문제.

접근

• 합의 최댓값을 구해야 하니 그리디 알고리즘을 통해 큰 숫자부터 골라서 더하는 방법으로 접근했다.
  • 그러나 이 문제의 경우 최댓값부터 더했을 때 정답이 아닌 경우가 존재한다.
  • 예제1인 합이 21이 되는 세 숫자도, [5, 6, 7, 8, 9] 에서 최댓값을 포함하지 않으며 [6, 7, 8] 을 더한 21이었다.
  • 여기서 그리디로 접근하면 안되겠다는 걸 알아차렸어야 했다..!
• 1시간정도 삽질을 하다가 결국 구글링의 도움을 받았고, 그리디가 아닌 브루트포스 알고리즘을 쓰는 문제였다.
  • 즉 주어진 카드에서 3개의 조합을 모두 구하고, 그 중에서 주어진 값에 가장 가까운 조합을 찾아야 한다.
  • 시간제한이 1초라 해결할 수 있을까? 했는데, 3장의 조합만을 찾는거라 그런지 가능했다..’0’
  • 그러고 보니 전에 조합을 공부하게 만들었던 일곱난쟁이 와 비슷하다. 알고 나서야 보이는구나.

풀이

• 카드 3장의 모든 조합을 찾는 것이므로 3중 for문으로 구할 수 있다. 조합을 구현해서도 풀 수 있을 것임!
• currentMax ≤ sum && sum ≤ totalMax 대신 Range.contains(sum) 를 사용해 봤는데 좋은 것 같다.

let input = readLine()!.split(separator: " ").map { Int($0)! }
let totalMax = input[1]
let count = input[0]
var cards = readLine()!.split(separator: " ").map { Int($0)! }
var currentMax = 0
for i in 0..<count {
    for j in i + 1..<count { // 직전 반복문에서 사용한 다음 요소부터 사용 - 중복 피하기
        for k in j + 1..<count {
            print(cards[i], cards[j], cards[k])
            let sum = cards[i] + cards[j] + cards[k]
            if (currentMax...totalMax).contains(sum) {
                currentMax = sum
            }
        }
    }
}
print(currentMax)