안녕하세요! 오늘부터 제가 풀었던 백준 문제에 대해 글을 써보려 합니다.
어제 글 작성한 것 같은데 안 올라갔나 보네요..
잔말 말고 바로 들어가 볼게요.
문제링크
B2 2798번 블랙잭
문제 설명
카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.
한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.
김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.
문제는 위와 같습니다.
하나씩 정리해 볼게요.
- 카드 개수 N과 제한 숫자 M을 알아야 한다.
- 카드 N장을 밑 줄에 입력한다.
- M을 넘지 않으면서 M과 최대한 가까운 수 3개를 더한 값을 출력해야 한다.
보면 for문을 돌리면 될 거라는 생각이 들어요. 먼저 입력값들 작성하고,
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0] // 카드 개수
let m = input[1] // 제한 숫자
let cards = readLine()!.split(separator: " ").map { Int(String($0))! } // 카드들편하게 함수 하나 만들게요.
func blackJack(n: Int, m: Int, cards: [Int]) -> Int {
var max = Int() // 최대값
for first in 0..<n { // 처음은 0부터
for second in first+1..<n { // 두번째는 처음보다 +1
for third in second+1..<n { // 세번째는 두번째보다 +1
// 세개를 더한 값
let now = cards[first] + cards[second] + cards[third]
if m - now == 0 { // m과 now를 뺐을 때 0이면 조건에 가장 적합하기에 바로 nowMax리턴
max = now
return max
} else if m - now < 0 { // 조건성립 안함
continue
} else {
if max < now { // max가 max보다 작을때만
max = now
}
}
}
}
}
return max
}
print(blackJack(n: n, m: m, cards: cards))제가 한 이 방법은 완전탐색(Brute Force) 알고리즘입니다.
조합 가능한 모든 경우의 수를 하나부터 열까지 값을 대입해서 찾는 방식이에요.
만약 시간제한이 더 빡빡하거나 n의 범위가 더 크다면 사용할 수 없습니다.
잘못된 정보는 지적해 주시면 감사하겠습니다.
