[백준] 2798번 블랙잭

 

 

문제

소스코드

#include<iostream>
#include<vector>
constexpr int MAX_N = 101;
constexpr int MAX_M = 300001;



int BS(int N, int M, std::vector<int>& v) {
	int result{};

	for (int i = 0; i < N; ++i) {
		for (int j = i + 1; j < N; ++j) {
			for (int k = j + 1; k < N; ++k) {

				int total_sum = v[i] + v[j] + v[k];

				//M보다 3개의 카드합이 작으면 
				if (M >= total_sum) {
					//이 전에 찾은 값보다 크다면 바꾼다.
					if (result < total_sum)
						result = total_sum;
				}
			}
		}
	}

	return result;
}

int main() {
	int N, M;
	std::cin >> N >> M;
	std::vector<int> v;

	int value{};
	for (int i = 0; i < N; ++i) {
		std::cin >> value;
		v.emplace_back(value);
	}

	std::cout << BS(N, M, v) << "\n";
}

 

후기

이 문제는 완전 탐색인 방법 중 하나인 BS(brute-force)를 사용해서 풀었다. 

브루트 포스란 컴퓨터의 빠른 계산 능력을 사용하여 모든 경우에 수를 확인하는 방법이다.

내가 푼 알고리즘은 시간 복잡도가  N^3이라서 매우 느리고 비효율적이지만 제한 개수가 적어서 시간 안에 풀 수 있는 문제이다. 물론 좀 더 좋은 알고리즘을 사용할 수 있지만 BS가 무엇인지 알아보는 기초 문제이기 때문에 정직하게 푸는 것이 좋다.

(실제로 FAQ에 쓰여있다.)

 

다른 방법 중 하나인 비트마스크도 배운 후 사용을 해보면 좋을 거 같다.

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/2798