문제

나의 풀이

# 1. 3장씩 더한 모든 값을 저장 (M보다 작거나 같은 수만 저장)
# 2. M이 있다면 M 출력
# 3. M이 없다면 M에서 sum을 뺀 절대값을 minus에 저장
# 4. 가장 작은 절대값을 가진 수의 index로 sum에서 해당 index의 값 출력

모든 경우의 수를 다 찾아봐야하는 완전 탐색문제이다.

N, M = map(int, input().split())
card = list(map(int, input().split()))

sum = []            # 세 수를 더한 값
minus = []			# 세 수를 더한 값에서 M을 뺀 값
min = abs((card[-1] + card[-2] + card[-3]) - M)  # 가장 큰 세 수 합에서 M을 뺀 값

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            total = card[i] + card[j] + card[k]
            if total <= M:
            	sum.append(total)			# 세 수의 합을 모두 리스트에 저장

if M in sum:
    print(M)		# 구하려는 M이 리스트에 있다면 바로 출력
else:
    for i in sum:		# 없다면 sum에서 M을 뺀 절대값을 minus에 저장
        minus.append(M - i)
        if min >= M-i:				# 가장 작은 절대값을 구함
            min = M-i

    idx = minus.index(min)			# 가장 작은 절대값을 가진 것의 index 값을 구함
    print(sum[idx])					# 그 인덱스를 가진 sum 값을 구함


# 5 17
# 5 6 7 8 9      -> 18이 가장 17과 가까운 수

# [18, 19, 20, 20, 21, 22, 21, 22, 23, 24]
# [1,  2,  3,  3,  4,  5,  4,  5,  6,  7]
#  v    절대값이 가장 작음

• M을 넘지 않는 수 중 가장 M과 가까운 값을 출력하는 건데
  그 조건을 빼먹어서 5번이나 틀렸다! 나는 바보~
• 그 조건을 일찍이 알아차렸다면 다른 방식으로 시도했을텐데 조건을 보지않고 틀린 이유만 찾느라 시간을 너무 많이 소모했다.

다른 풀이

1

N, M = map(int, input().split())
card = list(map(int, input().split()))
result = 0

for i in range(N):
	for j in range(i+1, N):
        for k in range(j+1, N):
        	if card[i] + card[j] + card[k] > M:
            	continue   # M보다 큰 값은 제외
            else:
            	result = max(result, card[i] + card[j] + card[k])

print(result)

2 - 순열과 조합 사용

from itertools import combinations

N, M = map(int, input().split())
card = list(map(int, input().split()))
biggest = 0

for cards in combinations(card, 3):
	total = sum(cards)
    if biggest < total <= M:
        biggest = total

print(biggest)

• 파이썬에서 제공하는 순열 조합 라이브러리 itertools 모듈의 combinations 함수 사용

순열과 조합 - combinations, permutations

• 1, 2, 3의 숫자가 적힌 카드가 있을 때, 두장을 꺼내는 경우의 수
  -> 12, 13, 21, 23, 31, 32
• A, B, C로 만들 수 있는 경우의 수 -> 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'
• for문을 사용하지 않고도 순열과 조합을 구할 수 있다.

import itertools

pool = ['A', 'B', 'C']
print(list(map(''.join, itertools.permutations(pool))))   # 3개의 원소로 순열 만들기
print(list(map(''.join, itertools.permutations(pool, 2))))  # 2개의 원소로 순열 만들기 

# ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
# ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']

순열과 조합