[파이썬/Python] 백준 2798번: 블랙잭

숨·2024년 7월 11일

코테

알고리즘 문제 풀이

목록 보기

26/105

📌 문제 : 백준 2798번

📌 문제 탐색하기

N : 카드 수 (3 ≤ N ≤ 100)
M : 카드 합 제한 (10 ≤ M ≤ 300,000)
card : 카드 숫자 (1 ≤ n ≤ 100,000)

✅ 입력 조건
1. N, M 입력
2. N개의 카드 숫자 입력
✅ 출력 조건
1. M을 넘지 않으면서 M과 가장 가까운 값 출력

먼저 N개 중 3개를 뽑는 경우를 고려해주어야 하므로, itertools의 combinations를 활용한다.

M과 가장 가까운 값을 가지는 3장의 카드의 합을 구해야 하므로,
3장 고르는 경우의 수 중에 그 카드들의 합과 M의 차이가 가장 적은 값을 구하도록 코드를 작성했다.
카드의 합과 M의 차이는 계산했을 때, 더 작은 차이가 나오면 그 값으로 갱신하도록 하여 가장 적은 차이가 나는 합을 찾도록 하였다.

가능한 시간복잡도

카드 숫자 입력 → $O(N)$
조합 생성 → $O(N^3)$
계산해 합 비교 → $O(1)$

최종 시간복잡도
$O(N^3)$ 으로 최악의 경우 1000000번의 연산을 하게 되는데, 이는 제한 시간 내에 연산이 가능하다.

알고리즘 선택

조합을 계산해 조건에 맞는 최댓값을 찾아가는 방법

📌 코드 설계하기

N, M 입력
N장의 카드 입력
정답과 값의 차이 저장할 변수 선언
N개 중 3개 고르는 조합 구하기
4-1. M을 넘지 않으면서 M에 가까운 카드의 합 갱신하며 구하기
원하는 형식으로 출력

📌 시도 회차 수정 사항

1회차

# M을 넘지 않으면서 M에 가장 가까운 카드의 합 구하기
if card_sum <= M and abs(card_sum - M) <= ans:
    ans = card_sum

카드의 합과 M의 차가 최소인 합을 찾기 위해 조건을 위와 같이 달았다. 생각해보니 ans엔 찾고자하는 카드 합이 들어있는데 abs(card_sum - M) <= ans와 같이 값의 차이를 최대 합과 비교하도록 코드를 완전히 잘못 작성했다.

# M을 넘지 않으면서 M에 가장 가까운 카드의 합 구하기
if card_sum <= M and abs(card_sum - M) <= differ:
    ans = card_sum
    differ = abs(card_sum - M)

값의 차를 저장할 변수를 따로 만들어주어 비교하는 코드로 변경하였다.

📌 정답 코드

import sys
from itertools import combinations

input = sys.stdin.readline

# N, M 입력
N, M = map(int, input().split())

# N장의 카드 입력
cards = list(map(int,input().split()))

# 정답 저장 변수 선언
ans = 0
differ = 300000

# N개 중 3개 고르는 조합 계산
for com in combinations(cards, 3):
    card_sum = sum(com)
    # M을 넘지 않으면서 M에 가장 가까운 카드의 합 구하기
    if card_sum <= M and abs(card_sum - M) <= differ:
        ans = card_sum
        differ = abs(card_sum - M)

# 원하는 형태로 출력
print(ans)

결과

다른 풀이 1

import sys
from itertools import combinations

input = sys.stdin.readline

# N, M 입력
N, M = map(int, input().split())

# N장의 카드 입력
cards = list(map(int,input().split()))

# 정답 저장 변수 선언
ans = 0

# N개 중 3개 고르는 조합 계산
for com in combinations(cards, 3):
    card_sum = sum(com)
    # M을 넘지 않으면서 M에 가장 가까운 카드의 합 구하기
    if card_sum <= M:
        ans = max(card_sum, ans)

# 원하는 형태로 출력
print(ans)

결과
조건식을 간소화한 코드이다.
M을 넘지 않아야 한다는 조건을 제대로 잊고, 값의 차이를 절댓값한 값으로 구해야 한다고 생각했다. 더 깔끔하게 풀 수 있는 방법이 있었다.

다른 풀이 2

import sys

input = sys.stdin.readline

# N, M 입력
N, M = map(int, input().split())

# N장의 카드 입력
cards = list(map(int,input().split()))

# 정답 저장 변수 선언
ans = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if cards[i] + cards[j] + cards[k] > M:
                continue
            else:
                ans = max(ans, cards[i] + cards[j] + cards[k])

print(ans)