boj 2798번 - 블랙잭

https://www.acmicpc.net/problem/2798

2798번: 블랙잭

브루트 포스라니 이름이 간지난다..

 

조합 문제다. 파이썬에는 콤비네이션 내장 함수가 있다...

 

from sys import stdin
from itertools import combinations

def main():
  def input():
    return stdin.readline().rstrip()
    
  N,M = map(int,input().split())

  ls1= list(map(int,input().split()))

  ls2 = combinations(ls1 , 3)

  tmp = 0
  pro = 300000

  for i in ls2:
    if M - sum(i)< pro and sum(i) <= M:
      tmp = sum(i)
      pro = M-sum(i)

  print(tmp)
  
if __name__ == "__main__":
  main()

콤비네이션 튜플을 담은 l2리스트를 만들고 반복 순회를 통해 차가 제일 작으면서 M을 넘지 않는 수를 반환한다.

pro변수를 300000으로 선언해줬고 tmp 를 통해 순회하며 가장 적합한 값이 계속 바뀔 수 있도록 만들어줬다.

 

복잡도 O(n)으로 시간적 제약조건을 초과하지 않는다.