[BOJ 2798] 백준 블랙잭 - C++

 

사용언어 :  C++

 

 

 

 

문제풀이

* brute force 사용하기

M을 넘지 않으면서 M에 최대한 가까운 카드 3장을 구해야 한다. 3장이니까 3중for문을 돌려준다. 

 

 

(1) N, M, 카드 숫자 입력받기

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

 

(2) 3중 for문을 돌려 순차탐색으로 M보다 크지않은 M과 가까운 최댓값 구해주기

arr[i], arr[j], arr[k]의 총합을 구한 뒤 현재 max_num과 비교한다. 만약 현재 max_num보다 크면서 M을 넘지 않을 때, max_num을 arr[i], arr[j]. arr[k]의 총합으로 바꿔준다. (이 때, break는 하지 않는다. M과 더 가까운 수가 있을 수 있기 때문)

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++) {
				int tmp = arr[i] + arr[j] + arr[k];
				if (tmp > max_num && tmp <= M) {
					max_num = tmp;
				}
			}
		}
	}

 

 

전체코드

#include <iostream>
using namespace std;

int arr[100];
int max_num = 0;
int main() {
	int N, M;
	cin >> N >> M;
	
	for (int i = 0; i < N; i++) {
		cin >> arr[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++) {
				int tmp = arr[i] + arr[j] + arr[k];
				if (tmp > max_num && tmp <= M) {
					max_num = tmp;
				}
			}
		}
	}

	cout << max_num;
}

 

 

 

총평

브루트포스의 기본 문제라고 생각하면 된다. 다만 삼중 for문을 돌릴 때 j,k의 시작값 설정 부분에서 실수를 해 한 번에 성공하지 못했다 ㅜㅜ  처음엔 i=0; j=1; k=2; 로 설정했다. 그러나 그렇게 되면 i가 다시 새로운 숫자로 바꼈을 때에도 j와 k는 여전히 1과 2에서 시작하게 된다. 그게 아닌 i=0; j=i+1; k=j+1; 로 설정해줘야 한다!

	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++) {
				int tmp = arr[i] + arr[j] + arr[k];
				if (tmp > max_num && tmp <= M) {
					max_num = tmp;
				}
			}
		}
	}

 

---

문제 출처

https://www.acmicpc.net/problem/2798

2798번: 블랙잭