[2798] 블랙잭

브론즈 2

 

브루트포스 알고리즘을 이용한다

브루트포스 알고리즘(Brute Force) : 완전탐색. 가능한 모든 경우의 수를 탐색하는 알고리즘

 

이런 식으로 더하면 빠짐없이 더할 수 있다

총 3개의 수를 골라야 하므로 for문 3개를 이용하였다

첫 번째 for문 : 첫 번째 수 더함 ( 앞으로 더할 수가 2개 더 있으므로 N-2까지 )

두 번째 for문 : 두 번째 수 더함 ( 앞으로 더할 수가 1개 더 있으므로 N-1까지 )

세 번째 for문 : 세 번째 수 더함 ( N까지 )

그리고 이것이 M을 넘지 않으면서 최대한 커야 하므로 if문으로 조건을 걸어준다

 

for문 중간중간마다 sum이 M을 넘어가버릴 경우 continue로 계산을 멈춰주었다

#include <iostream>
using namespace std;

int N, M;

int A[101];
int maximum = -1;
int sum;

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	for (int i = 0; i < N - 2; i++) {
		sum = 0;
		sum += A[i];
		if (sum > M) continue;

		for (int j = i + 1; j < N - 1; j++) {
			sum += A[j];
			if (sum > M) { // sum이 M을 넘어버리면 조건 어긋나므로
				sum -= A[j];
				continue;
			}

			for (int k = j + 1; k < N; k++) {
				sum += A[k];
				if (sum > M) {
					sum -= A[k];
					continue;
				}
				if (sum > maximum) maximum = sum;

				sum -= A[k];
			}

			sum -= A[j];
		}
	}

	cout << maximum;
}