[백준-2798] 블랙잭 파이썬, 3중 반복문 사용

# 문제

# 풀이

 문제를 너무 어렵게 생각했다. 알고리즘 공부를 막 시작한터라 시간복잡도에 얽매이면서 뭔가 코드를 가장 효율적이게 짜야한다는 생각에 휩싸였다. 

## 실패한 풀이1

 맨 처음에는 백트래킹방법으로 조건에 맞는 가지치기를 하려고 했다. 이것도 틀린 풀이가 될 것 같지는 않았는데, 어제 공부했던 백트래킹인데 막상 구현하려니 헷갈려서 다른 방법을 찾아보려고 했다. 

## 실패한 풀이2

 이번엔 3중 반복문을 사용하면서 비교하도록 했다. 결국에 이렇게 푸는게 정답이었는데, 나의 뭔지 모르는 자신감이 정답을 산으로 가게 만들었다. 나름 효율성을 생각한다고.. 가장 큰값 하나는 무조건적으로 선택 될 것이라는 말도 안되는 생각이 [예제 입력2] 케이스를 넘지 못하게 했다. 풀면서 생각해보니까 정말 어디서 나온 근거인지 모르겠다.

## 정답 풀이

 3중 포문을 돌리면 됐다. 입력조건에서 카드는 100가지라고 했기때문에 조합의 공식으로 생각해봐도  (100*99*98)/100! == 1,000,000 백만 가지수 밖에 되지 않는다고 했다. 파이썬은 1초에 2천만회의 연산을 수행한다고 한다.

 뭔가 n*n연산만해도 엄청 느릴거 같아서 n*n*n은 정말 느리겠지 했는데, 문제에 따라서 다른 것 같다는 생각이 들었다.

 

# 코드

"""
  파이썬은 1초에 대략 2천만번 연산을 수행
  조합공식을 이용했을때 최대 100만가지밖에 안되기 때문에 3중반복문으로 모든 경우의 수를 더하면 됨
"""
import sys

def solve(N,M,cards):
  size_card = len(cards)
  max = 0

  for i in range(size_card):
    for j in range(i+1,size_card):
      for k in range(j+1,size_card):
        check = cards[i] + cards[j] + cards[k]
        if check > max and check <= M:
          max = check
  return max


if __name__ == '__main__':
  N,M = list(map(int,sys.stdin.readline().strip().split()))
  cards = sorted(list(map(int,sys.stdin.readline().strip().split())),reverse=True)
  answer = solve(N,M,cards)
  print(answer)

 

# 후기