문제 링크 : https://www.acmicpc.net/problem/2798
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
N, M = map(int,input().split())
li = list(map(int, input().split()))
result = 0
for i in range(0,N):
for j in range(i+1,N):
for k in range(j+1,N):
temp = li[i]+li[j]+li[k]
if temp > M:
continue
if result<temp:
result=temp
print(result)
가장 기본적인 방법부터 생각해보면 브루트포스(Brute Force)가 생각이 난다.
N<100 으로
시간 복잡도가 N^3의 경우 1000000으로 시간 초과 문제도 발생하지 않기 때문에 브루트 포스를 이용해서 풀었다.
주의할점은 for 문의 시작점인데
i는 0부터
j는 i보다 1큰곳 부터
k는 j보다 1큰곳 부터 시작해줘야 중복이 발생하지 않고 모든 경우를 체크 해 볼 수 있다.
