티스토리 뷰

코딩테스트/백준

[백준/python] 2798번 - 블랙잭 / CLASS 2

sikaro 2023. 12. 12. 13:08
반응형

 

 

2798번: 블랙잭

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장

www.acmicpc.net

 

풀이

import sys
from itertools import combinations

n,M=map(int,sys.stdin.readline().split())
li=map(int,sys.stdin.readline().split())
b=0
a=list(map(sum,list(combinations(li,3))))
a.sort()
for i in a:
    if i>M:
        b=a.index(i)
        break
print(a[b-1])

 

필자는 모든 콤비네이션을 구하고, map을 통해 더해 그를 활용하는 코드를 작성하였다.

 

모든 콤비네이션을 sort 하면 오름차순 정렬이 되고, 만약 그 숫자가 M이 넘어간다면 바로 break 하도록 했다.

 

직관적으로 간단한 코드이다. 그러나 시간 복잡도 면에서 combations는 아쉬움이 있다.

 

다음은 1위의 코드이다.

import sys
N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)

mx = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    for k in range(j+1, N):
      s = arr[i]+arr[j]+arr[k]
      if s<=M:
        if mx < s: mx = s
        break

print(mx)

 

for을 세번이나 써서 풀이했다. 그럼에도 불구하고 직관적이다.

범위가 N-2, N-1, N이 되는 이유는 각 숫자마다 범위가 달라지기 때문. 예를 들어 5의 조합을 전부 썼다면 그 다음에는 6부터 쓰는 셈이다.

 

그런 식으로 s를 더해서 M과 비교하는데, M보다 작다면 mx를 갱신한다.

 

그래서 최종 답이 mx가 되는 셈. 확실히 1위의 코드는 다르다.

반응형