[Swift] 백준 2798번 블랙잭

문제 출처: 백준 2798번 블랙잭

문제

---

풀이

---

입력받은 카드 중에서 3장을 뽑아 주어진 M과 가장 가까운(최댓값) 경우의 수를 구하는 문제입니다. 처음 이 문제를 읽어보고 조합이 떠올라 재귀함수를 이용해 풀어보았습니다.

/// 첫째 줄 입력
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
/// 카드의 개수
let N = input[0]
/// 카드의 합
let M = input[1]
/// 카드에 쓰여있는 수
let cards = readLine()!.split(separator: " ").compactMap { Int($0) }
/// 카드들의 합
var sum = 0
/// 카드 3장의 합들중 M을 넘지않는 수를 담아둘 배열
var arr: [Int] = []

func Combination(count: Int, idx: Int) {
  // 선택한 카드의 수가 3일 경우
  if count == 3 {
    // 선택한 카드들의 합이 M보다 작을 경우 append
    if sum <= M {
      arr.append(sum)
    }
    return
  }
  
  // 마지막 카드일 경우
  if idx == cards.count {
    return
  }
  
  // 카드 한장을 선택해 sum에 합산
  sum += cards[idx]
  // 카드 한장을 선택한 상태에서 다음 카드 계산
  Combination(count: count + 1, idx: idx + 1)

  // 선택한 카드 취소
  sum -= cards[idx]
  // 현재 카드를 선택하지 않고 다음 카드 계산
  Combination(count: count, idx: idx + 1)
}

// 조합 실행
Combination(count: 0, idx: 0)

// 결과 출력
print(arr.max()!)
}

1. 첫째 줄을 입력받아 “ “기준으로 나누어 Int 형으로 각각 N, M에 저장합니다.
2. 둘째 줄 카드의 종류를 “ “기준으로 나누어 Int 형으로 저장합니다.
3. 재귀함수를 이용해 처음부터 끝까지 모든 경우의 수를 구합니다.
4. 조건에 맞게 구한 값 중 최댓값을 출력합니다.

이렇게 풀 경우 메모리: 72232 KB, 시간: 20 ms 결과가 나오게 됩니다.

다른풀이

---

알아보니 굳이 이렇게 조합을 사용하지 않고 결국 카드는 3장만 뽑으면 되기에 삼중 반복문을 통해 푸는 분들이 많았습니다.
평균적으로 Combination보다 시간이 더 적게 걸리는데요… 왜 이런 결과가 나오는지 아직 잘 모르겠습니다… 혹시 아시는 분이 있다면 댓글 부탁드립니다.
그러면 삼중 반복문의 경우에 관해 설명하자면 [5, 6, 7, 8] 배열이 주어졌을 때
[5, 6, 7], [5, 6, 8], [5, 7, 8], [6, 7, 8]
총 4가지의 경우의 수가 생깁니다.
숫자들의 규칙을 생각하면서 로직을 생각해보면

1. 주어진 배열 전체를 반복하면서 -> 첫 번째 카드
2. 1번에서 선택한 다음 카드 -> 두 번째 카드
3. 2에서 선택한 카드 다음 카드부터 끝까지 -> 세 번째 카드

이렇게 정의할 수 있습니다.

/// 첫째 줄 입력
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
/// 카드의 개수
let N = input[0]
/// 카드의 합
let M = input[1]
/// 카드에 쓰여있는 수
let cards = readLine()!.split(separator: " ").compactMap { Int($0) }
/// 정답
var result = 0

// 첫 번째 카드
for i in 0..<cards.count {
  // 두 번째 카드
  for j in (i + 1)..<cards.count {
    // 세 번째 카드
    for k in (j + 1)..<cards.count {
      // 겹치지 않으면서 선택한 세 카드의 합
      let sum = cards[i] + cards[j] + cards[k]
      
      // M 이하일 경우 현재 값과 sum중 최댓값 
      if sum <= M {
        result = max(result, sum)
      }
    }
  }
}

// 결과 출력
print(result)

깔끔하게 설명하고 싶었는데 아직 부족한거 같습니다…