백준 2798번
https://www.acmicpc.net/problem/2798

---

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

---

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

---

생각하기

전체를 탐색하지 않고 최대값 부터 시작해서 회전을 한다면
첫번째 나오는 값이 구할 수 있는 최대값이라고 생각해서 문제를 풀었는데,
내가 원하는 답이 나오지 않아서 그냥 부르트포스 를 사용하기로 했다.

결과값이 M보다 작거나 같은 값들은 result 리스트에 저장하고,
result 리스트에서 가장 높은 값을 출력하면 정답이 된다.

일단 효율적인 반복을 생각해서 처음 카드 값들을 list에 저장할 때 M 보다 큰 값이 있을 경우도 있을 수 있으니 미리 list 저장단계에서 M보다 큰 값들은 제외하고 list에 저장하도록 한다.

카드들의 숫자를 list에 저장후 list의 값들을 역순으로 정렬했는데 여기서 정렬한 이유를 설명하자면, 총 3장의 카드를 뽑아야 하니 3개의 for문을 쓸 생각을 했다.
역순정렬 이므로 첫 번째 i for문에서 처음 값을 뽑으면 당연히 가장 큰 값을 뽑게 된다.

이후 두 번째 j for문에서는 i+1의 카드를 뽑고 다시 k for문으로 넘어가면서 j+1의 카드를 뽑으며 가장 높은 값부터 하나씩 줄여가며 찾는다면, 첫번째로 나오는M과 같거나 작은 조건에 부합하는 카드의 합이 블랙잭에서 가장 큰 값이 될 거라고 생각했기 때문인데, 돌려서 결과를 확인해보니 내가 원하는 값이 나오지 않았다.

이제 작성된 코드로 돌아가서N이 10 M이 500, 카드가 93 181 245 214 315 36 185 138 216 295 일때,

부트르 포스 방식을 썼기때문에 3장의 카드를 3개의 for문을 사용해서 완전탐색을 한다고 생각하면 된다.
(가장 가까운 예시를 들어 시계라고 생각해보자 시침과 분침 초침의 회전이라고 생각하면 쉽다.
시침이 움직이기 이전에 분침이 움직여야 하고 분침이 움직이기 전에 초침이 회전해야 하는 원리이다.)

첫번째 카드를 가장앞에것으로 뽑으면 두번째 카드는 2번째 위치한카드 세번째 카드는 3번째에 위치한 카드 값 그리고 해당 카드값의 합이 500을 넘었다면 첫번째 두번째 카드값은 유지하고 세번째 카드만 다시 4번째 카드를 뽑으면서 합을 계산하는 방식으로 회전한다.

500이하로 만들 수 있는 카드조합을 찾고 이 조합의 합을 result 리스트에 저장 후 가장 큰 값이 정답이 되는 원리이다.

여기서 중간중간 필요없는 부분은 뛰어 넘을 필요가 있기때문에 if문을 통해서 걸러주는 코드를 작성했다.

예를 들자면 first값 즉, 첫번째 카드가 list를 역순으로 정렬했을 때, 315가 되고, list의 가장 작은 값 min은 36이 된다. 이런 경우는 두번째 카드second 와 첫번째 카드first 값의 합이 M을 넘을 경우는 해당 second 카드는 건너뛰는 구조로 만든다면 불필요한 회전을 최대한 줄일 수 있다.

TMI

복잡하긴 하지만 그렇게 어렵지 않은 난이도의 문제 였던것 같다.
처음 생각했던 방식대로 진행되지 않아서 답답했지만

부르트포스 방법이 잘 먹혀서 다행인것 같다
1트만에 성공, 나름 Easy하게 해결!

---

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		List<Integer> list = new ArrayList<>();
		List<Integer> result = new ArrayList<>();

		for(int i=0; i<N; i++) {
			int temp = (Integer.parseInt(st.nextToken()));

			if(temp >= M) {
				continue;
			}
			else {
				list.add(temp);
			}
		}

		Collections.sort(list, Collections.reverseOrder());

		int first = 0;
		int second = 0;
		int third = 0;
		int size = list.size();
		int min = list.get(size-1);
		int min2 = list.get(size-2);

		for(int i=0; i<size; i++) {			
			int sum = M;
			first = list.get(i);
			int sum1 = first;
			int sum2 = 0;
			int sum3 = 0;

			for(int j=i+1; j<size; j++) {
				second = list.get(j);
				sum2 = sum1 + second;

				if(sum2 <= (M-min)) {

					for(int k=j+1; k<size; k++) {
						third = list.get(k);
						sum3 = sum2 + third;
						if(sum3 <= M) {

							if(sum - sum3 >= 0) {
								result.add(sum3);
							}
							else {
								sum3 = sum2;
							}

						}

					}

				}

				sum2 = sum1;
			}

		}

		System.out.println(Collections.max(result));
	}
}