[C++] 백준 온라인 저지 2798, 블랙잭

문제

---

www.acmicpc.net/problem/2798

2798번: 블랙잭

설계

---

브루트포스는 '모든 경우의 수'를 탐색하는 알고리즘이다.
말 그대로 '무식한 힘' 알고리즘이다.
장점으로는 정답을 100% 찾아낼 수 있다는 것이지만, 단점은 당연히 효율이 극단적으로 떨어진다는 것이다.

하지만 브루트포스가 오히려 코드가 간결한 문제들이 몇 개 있다. 이런 문제 같은 경우다.

먼저 변수들을 선언해주고 필요한 정보를 입력해줬다.

n과 m은 문제에 있는 그대로고, sum은 최대값을 비교하기 위한 값, 즉 일시적인 숫자들을 더한 값 이고,
max는 최대값, 즉 정답이다.
card는 배열로 선언해줬다.

int n, m, sum =0, max = 0;
cin >> n >> m;
int card[n];
for(int i = 0; i < n; i++){
	cin >> card[i];
}

그리고 말그대로 모든 수들을 돌면서 더해보면 된다.
다음과 같은 배열들을 모두 탐색한다.

card[0] + card[1] + card[2] = 012 이런식으로 표기하도록 하겠다.

012 013 014
023 024
034
123 124
134
...

이런식으로 모두 돌면서, 더한 값이 max보다 큼과 동시에 m을 넘지 않는다면 max로 바꿔주도록 한다.

for(int i = 0; i < n - 2; i++){
	for(int j = i + 1; j < n - 1; j++){
		for(int k = j + 1; k < n; k++){
			sum = card[i] + card[j] + card[k];
			if(sum <= m && sum >= max)
				max = sum;
		}
	}
}

 

코드

---

#include <iostream>
using namespace std;

int main() {
    int n, m, sum =0, max = 0;
    cin >> n >> m;
	int card[n];
	
	for(int i = 0; i < n; i++){
		cin >> card[i];
	}
	
	for(int i = 0; i < n - 2; i++){
		for(int j = i + 1; j < n - 1; j++){
			for(int k = j + 1; k < n; k++){
				sum = card[i] + card[j] + card[k];
				if(sum <= m && sum >= max)
					max = sum;
			}
		}
	}
	cout << max << '\n';
}

 

결과

---

브루트 포스는 정말 단순하게 생각하면 된다.
그냥 이런게 있구나 정도로 코딩하면서, 조건을 어떻게 잘 짜야 하는지 생각하는 것이 관건인 것 같다.

 

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡