BOJ/2798

블랙잭

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {

int cnt;
int arr[100];
int M;

scanf("%d", &cnt);
scanf("%d", &M);

for (int i = 0; i < cnt; i++) {
scanf("%d", arr + i);
}

int a, b, c;
int sum;
int diff;
int past_diff = M; // 나올 수 없는 가장 큰 오차부터 시작.

for (int i = 0; i < cnt; i++) {
for (int j = 0; j < cnt; j++) {
for (int k = 0; k < cnt; k++) {
if (i == j || j == k || i == k) {
//패스(같은 카드 고르는 경우가 없어야..)
}
else {
sum = arr[i] + arr[j] + arr[k];
diff = M - sum;

if (diff >= 0 && diff < past_diff) {
past_diff = diff;
}

}
}
}
}

printf("%d", M - past_diff);

return 0;
}

 

 

브루트포스 알고리즘. 나올 수 있는 모든 경우를 판단. 전수조사.

3중 for문이며, cnt에 대하여 모든 for문이 작동함으로 빅오표기법 O(n^3)