[백준/python3] 2798_블랙잭(brute force)

 

 

import sys

n, m = map(int, sys.stdin.readline().split())
cards = list(map(int, sys.stdin.readline().split()))
cards.sort() 

'''
카드를 오름차순으로 정렬.
밑에 break문을 써주었으므로, 마지막에 인덱스가
012, 013, 014 이런 식으로 돌아야 하는데
012에서 m보다 값이 커지면 k for문이 돌지 않음

정렬을 안 쓰려면 아래 break 대신 continue 써줄 것
단 continue를 쓰면 시간복잡도 O(n^3)을 다 돌게 되는데,
정렬한 후 break를 걸면 m 이상인 수가 된 순간부터 뒷부분 돌지 않아서
시간 복잡도 감소함
'''

cards_li = [] # 3장의 카드 합을 담는 리스트


for i in range(n-2) : # 맨 첫 장부터 n-2까지 도는 거
    for j in range(i+1, n-1) : # 그 다음 장부터 n-1까지 도는 거  
        for k in range(j+1, n) : # 3번째 장부터 마지막 장까지 도는 거
            sum_3cards = cards[i]+cards[j]+cards[k]
            if sum_3cards > m : # 카드 합이 m을 넘어서면 멈춤
                break
            cards_li.append(sum_3cards) # m보다 작은 3장의 합들만 리스트에 추가


print(max(cards_li)) # 리스트 중 max값 출력




''' 시작 부분을 0, 1, 2로 고정했을 때

for i in range(n-2) :
    for j in range(1, n-1) :
        for k in range(2, n) :
            으로 했을 때 
            
[18, 19, 20, 19, 20, 21, 20, 21, 22, 19, 20, 
21, 20, 21, 22, 21, 22, 23, 20, 21, 22, 21, 22, 
23, 22, 23, 24]

이렇게 뜸

반복문 시작하는 자리가 고정 되어 있기 때문에 코드가 이상하게 돎

5+6+7 = 18, 5+6+8 = 19, 5+6+9=20, 5+7+7 = 19, 5+7+8 = 20으로 쓰이며
5+7+7이 다시 나옴

그러므로, 시작하는 자리를 0,1,2로 고정해두지 말고
0, i+1, j+1로 바꿔줄 것 


'''

 

# 다른 코드 1 - def 함수 이용


def check_plus(a):
    if a <= in_put[1]:
        answer.append(a)
 
in_put = input()
in_put = in_put.split(" ")
in_put = list(map(int, in_put)) #처음 입력값을 받아 N과 M을 분리
# N = in_put[0]  , M = in_put[1]
 
card = input()
card = card.split(" ")
card = list(map(int, card)) #각 카드의 값을 리스트화
 
 
answer = [] # M을 넘지 않는 각 카드의 합
for i in card:
    compare = card[:] #lits card의 값이 사라지면 곤란하므로
    m_answer = 0
    m_answer += i
    f_num = m_answer
    compare.remove(i) #첫번째 카드를 더하고, 리스트에서 제거
    for j in compare:
        m_num = f_num # 첫 카드를 뽑은 값으로 돌아오기 위함.
        m_num += j
        compare.remove(j)
        for k in compare:
            l_num = m_num #두번째 카드까지의 합으로 돌아오기 위함.
            l_num += k
            check_plus(l_num)
 
print(max(answer))

# 다른 코드 2


import sys

n, m = map(int, sys.stdin.readline().split())
cards = list(map(int, sys.stdin.readline().split()))

result = 9999999
for i in range(n-2) : # 맨 첫장부터 n-2까지 도는 거
    # sum_3cards = 0
    for j in range(i+1, n-1) : # 그 다음장부터 n-1까지 도는 거
        for k in range(j+1, n) : # 3번째 장부터 마지막장까지 도는 거
            sum_3cards = cards[i]+cards[j]+cards[k]
            if m - sum_3cards <= result and m>=sum_3cards:
                result = m - sum_3cards
print(m-result)

 

 

<또다른 풀이 법>

백준 2798번 파이썬 문제풀이(브루트 포스- 블랙잭)

코드 1. for문과 중복 제거하는 set이용

코드 2. 파이썬 내장함수인 combinations 이용

백준 2798번 파이썬 문제풀이(브루트 포스- 블랙잭)