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번 파이썬 문제풀이(브루트 포스- 블랙잭)
코드 n, m = map(int, input().split()) inputNumList = list(map(int,input().split())) #입력을 받아 리스트에 저장 sumSet = set() #중복을 허용하지 않는 set자료형 선언(입력받은 숫자 중 3개의 숫자 합을..
ji-gwang.tistory.com
'python3 > 백준문제풀이' 카테고리의 다른 글
[백준/python3] 2839_설탕 배달(DP, Greedy) (0) | 2022.01.16 |
---|---|
[백준/python3] 23351_물 주기(Greedy) (0) | 2022.01.16 |
[백준/python3] 2775_부녀회장이 될테야 (0) | 2022.01.16 |
[백준/python3] 4673_셀프 넘버(brute force) (0) | 2022.01.15 |
[백준/python3] 5622_다이얼 (0) | 2022.01.13 |