백준 알고리즘 - 2798 - 블랙잭

10 500

93 181 245 214 315 36 185 138 216 295

---

접근법

1. 카드의 개수(N)와 넘지 않는 양의 정수(M) 입력 받기
2. 카드 입력 받기 (card)
3. 카드 3장 뽑기 (All)
4. 3장의 합이 500보다 작은 것들 중 가장 큰 것 추출

 

for 문을 3번이나 써야해서 망설였다.

---

내 풀이

N, M = map(int, input().split())
arr = list(map(int, input().split()))
sum = list()
ans = list()

for i in range(N-2):
  a = arr[i]
  for j in range(i+1, N-1):
    b = arr[j]
    for k in range(j+1, N):
      c = arr[k]
      sum.append(a+b+c)

sum.sort()
for i in sum:
  if i <= M:
    ans.append(i)

print(ans[-1])

a, b, c 변수에 다 하나씩 저장하기 때문에 메모리를 더 많이 쓴다.

또한 시간도 더 많이 쓴다.

 

전체 합을 저장하는 sum 리스트를 만들어 정렬한 후,

M보다 작은 값을 ans 리스트를 만들어 추가한 다음,

맨 마지막 것을 출력하는 방법도 시간과 메모리를 더 많이 잡아 먹는다.

---

다른 풀이

N, M = map(int, input().split())
card = list(map(int, input().split()))
result = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            sum = card[i] + card[j] + card[k]
            if sum <= M:
                result = max(result, sum)
print(result)

 

위와 같이 a,b,c 변수를 만들 필요 없이

각각의 수를 한번에 더한 다음, sum에 저장하고

sum이 M보다 작거나 같을때

전까지 저장했던 result와 sum을 비교하여 

max()로 더 큰 값을 갱신해준다.

 

가장 깔끔한 코드가 된다.

---

다른 풀이

from itertools import combinations

N, M = map(int, input().split())
card = list(map(int,input().split()))
All = list(combinations(card, 3))
tmp = 0

for i in range(len(All)):
    if sum(All[i]) <= M and sum(All[i]) >= tmp:
        tmp = sum(All[i])
print(tmp)

 

3장의 카드의 조합을 구하면 3장의 카드를 뽑는 결과와 똑같다.

itertools의 combinations를 이용하면 조합을 구할 수 있다.

 

이 3장의 카드의 합을 하나씩 비교하여 

M 보다 작으면서 가장 합이 큰 것을 추출한다.