백준 2798. 블랙잭 파이썬

풀이 1번. 시간초과.

대강 조합을 사용해서 길이가 3인 조합을 찾고

다 더한 다음에 찾아야 하는 M을 반복문을 돌면서 하나씩 줄였다.

답은 잘 나와서 제출했는데 시간초과!

그냥 i번은 한 번 스쳤으면 (조합이니까 중복 된 값 안 씀) 그 다음 값 부터 찾으면 된다. 

조합 리스트의 길이가 길다면 재귀나 다른 함수를 써야 하는데, 고작 3이라서 완전탐색으로 반복문 돌리면 된다.

# M을 넘지 않으면서 최대한 가깝게
# 완탐으로 풀자.
# 3장을 모두 더해보고 혹시 21이 있니? 20이 있니? 19가 있니? 이렇게 물어봐야겠다.
# 길이가 3인 조합 맨드는 거 아뉴?
# N, M = map(int,input().split())
# card_num = list(map(int,input().split()))
# result = 0
# lst = []
# for i in range(N):
#     for j in range(i+1,N):
#         for k in range(j+1,N):
#             lst.append((card_num[i],card_num[j],card_num[k]))
# for i in range(len(lst)):
#     lst[i] = sum(lst[i])
# for i in range(M,-1,-1):
#     if i in lst:
#         result = i
#         break
#
# print(result)

 

풀이2. IM시험이 코앞이라 더 생각할 시간이 읎어서 유튜브 문어박사님 코드 참조. 

생각해보니 반복문으로 값 하나하나 돌릴 필요 없이, 그냥 M까지의 범위 내의 최댓값을 찾으면 되는 거 였다. 

# M과 같거나 작은 합의 최대값
N, M = map(int, input().split())
card_num = list(map(int, input().split()))
result = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if result < card_num[i] + card_num[j] + card_num[k]<= M:
                result = card_num[i] + card_num[j] + card_num[k]
print(result)

 

+괜히 visited로 방문 했는지 안 했는지 찾는다고 고생했다. 그럴 필요 없는데....

+ 그리고 조합을 재귀로 잘 구현 못한다. 시험 끝나고 다시 연습해봐야겠다.