반응형
[ Contents ]
1. 문제 (링크 참조)
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
2. 문제 풀이
N장에 카드 중 3장을 뽑아, M에 가장 가까운 수를 만드는 문제입니다.
2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?
[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?
[ Contents ] 1. 브루트 포스란? Brute(짐승 같은, 난폭한) + Force(힘, 폭력)의 합성어입니다. 무식하게 푸는 기법으로, '노가다'에 가까운 접근법입니다. 모든 경우의 수를 시험해보며 문제를 해결합니
star7sss.tistory.com
모든 경우의 수를 고려하는 브루트 포스 문제입니다. N장의 카드 중 3장을 뽑을 조합을 모두 구하고, 세 수의 합이 M과 가장 가까운 값을 찾아냅니다.
3. 코드
import itertools
N, M = map(int, input().split())
card = list(map(int, input().split()))
case = list(itertools.combinations(card, 3)) # N장의 카드 중 3장 선택할 경우의 수
res = 0
for i in case:
if M-sum(i) >= 0 and res < sum(i): #M을 넘지 않으면서, 여태까지의 최댓값보다 크면 갱신
res = sum(i)
print(res)
파이썬은 itertools 라이브러리를 이용하면 쉽게 순열, 조합을 구현할 수 있습니다. 라이브러리 및 함수에 대한 설명은 위 링크("브루트포스는 노가다 기법?")에서 찾아보실 수 있습니다.
반응형
'Algorithm' 카테고리의 다른 글
[수학/소수] 백준 2581 소수 - Python (0) | 2022.02.09 |
---|---|
[구현/수학] 백준 10250 ACM호텔 - Python (0) | 2022.02.09 |
[수학/소수] 백준 1929 소수 구하기 - Python (0) | 2022.02.08 |
[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 (0) | 2022.02.08 |
[구현] 백준 10995 별 찍기 - 20 - Python (0) | 2022.02.08 |
댓글