Where who wants to meet someone

백준 Swift [2798] 블랙잭 본문

백준 알고리즘 문제 기록/브루트 포스

백준 Swift [2798] 블랙잭

Lust3r 2023. 7. 3. 17:42
728x90

난이도

브론즈 II

 

문제

https://www.acmicpc.net/problem/2798

 

2798번: 블랙잭

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장

www.acmicpc.net

 

내 답안

let input = readLine()!.split(separator: " ").map { Int($0)! }

let n = input[0]
let m = input[1]

var cards = readLine()!.split(separator: " ").map { Int($0)! }
var nearSum = 0

for i in 0...n - 3 {
    for j in i + 1...n - 2 {
        for k in j + 1...n - 1 {
            let sum = cards[i] + cards[j] + cards[k]
            if sum <= m && sum > nearSum {
                nearSum = sum
            }
        }
    }
}

print(nearSum)

다 분리를 하고 나서 이제 카드 3장을 뽑아야 한다.

처음에는 첫 for문의 범위를 cards.indices로 잡으니 i가 뒤쪽에 있을 때 앞에 카드를 어떻게 선택할지가 문제였다.

다르게 생각해보면 중복되는 부분은 보지 않아도 되니까, 가령 첫 번째 수로 모든 경우를 다 돌았으면 두 번째 수에서는 첫 번째 수가 포함되지 않는 수만 봐도 되지 않을까? 했다.

 

그래서 첫 번째 for문은 뒤에 두 숫자가 더 있어야 하므로 n - 3까지 진행하고(배열이 0부터 시작하므로 추가적으로 1 빼주기),

두 번째 for문은 i 다음 인덱스부터 마지막 카드를 고려한 n - 2까지 진행, 세 번째 for문은 j 다음 인덱스부터 배열 마지막인 n - 1까지를 범위로 잡고, 배열의 각 인덱스 값을 더해 sum에 담고(뒤에서 여러 번 사용하기 때문에 프로퍼티를 만들었다)

그 sum이 m을 넘지 않으면서 기존의 nearSum보다 크다면 nearSum을 업데이트 하는 식으로 진행하였다.

 

저작자표시 비영리 변경금지

'백준 알고리즘 문제 기록 > 브루트 포스' 카테고리의 다른 글

백준 Swift [19532] 수학은 비대면강의입니다  (0) 2023.07.06
백준 Swift [2231] 분해합  (0) 2023.07.04
'백준 알고리즘 문제 기록/브루트 포스' Related Articles more