[항해]알고리즘 스터디(백준 #2798)

백준#2798

바로가기

문제 해석
우리가 풀어야 할 게임의 규칙은 카드의 개수 N개 중에서 3장을 선택해 합한 값이 M을 넘지 않으면서 최대한 가까워야 이긴다는 것이다.
카드 N개는 모두 숫자가 보이게 배치된다.
이 때, 우리가 이기기 위해 선택하는 카드 3장의 합을 출력하는 문제다.

입출력 규칙
1. 입력
첫째 줄에 카드의 개수 N과 위닝넘버 M
---예시) 5 21
둘째 줄에 카드 N개에 쓰인 번호들
---예시) 5 6 7 8 9
2. 출력
카드 N개 중 3개를 합한 값. 위닝넘버 M보다 작거나 같아야 한다.
---예시) 6, 7, 8을 합하게 되면 21

문제 접근
순서와 상관 없고, 중복 없이 3개의 숫자를 합하여 M보다 작거나 같은 결과를 출력해야 한다.
브루트포스 방식으로 한다. (5+6+7), (5+6+8), (5+6+9), (5+7+8), (5+7+9) ...등 모든 경우의 수를 탐색해서 M에 가장 가까운 경우를 출력하면 된다.

코드

n, m = map(int, input().split())
numlist = list(map(int, input().split()))
answer = 0
for i in range(len(numlist)):
    for j in range(i + 1, len(numlist)):
        for k in range(j + 1, len(numlist)):
            sum = numlist[i] + numlist[j] + numlist[k]
            if sum <= m:
                answer = max(answer, sum)
print(answer)