Python3
문제
https://www.acmicpc.net/problem/2798
키워드
- 브루트포스
문제 풀이
문제 요구사항
- N장의 카드 중에서 3장의 카드를 고른다.
- 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
- 첫 째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다.
- 둘 째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.
- 합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.
변수 및 함수 설명
- n: 카드의 개수
- m: 카드가 목표하는 합
- card: 카드에 쓰여져 있는 수 리스트
- jack: 현재 카드의 합
풀이
- 순서대로 카드를 뽑을 필요는 없고, 가장 m과 가까워질 수 있는 카드를 뽑으면 된다.
=> 브루트포스 사용 (brute: 무식한, force: 힘)
완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. - 삼중 반복문이 필요하다.
(입력과 선언)
- n, m과 카드에 쓰여져 있는 수를 입력 받는다.
- 현재 카드의 합이 들어 갈 변수 jack을 선언한다.
(반복문)
- 문제 1번 입출력 예시로 가정하면,
> 5 21
5 6 7 8 9
i j k
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4 - card[i] + card[j] + card[k] 가 목표한 합인 m보다 크면 건너뛴다.
- 그렇지 않으면, jack 값과 card[i] + card[j] + card[k] 값을 비교해 더 큰 값을 jack 변수에 넣는다.
최종 코드
n, m = map(int, input().split())
card = list(map(int, input().split()))
jack = 0
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
if card[i] + card[j] + card[k] > m:
continue
else:
jack = max(jack, card[i] + card[j] + card[k])
print(jack)(+23/5/25 combination으로 풀기)
from itertools import combinations
n, m = list(map(int, input().split()))
card = list(map(int, input().split()))
jack = combinations(card, 3)
ans = []
for i in jack:
if sum(i) <= m:
ans.append(sum(i))
print(max(ans))스터디 피드백
코드에서 card[i] + card[j] + card[k] 가 2번 이상 사용되었다.
이럴 때는 변수 하나에 담아서 사용하는 것이 시간 효율성 측면에서 좋다.
2, 3차원 배열을 자주 접근하게 되면 속도가 매우 느려지기 때문이다.
따라서 자주 접근할 것 같으면 변수에 저장하고 사용하는 습관을 들이자!
I mean