[추석맞이 코딩챌린지③] 블랙잭 c

문제 출처 : https://cafe.naver.com/codeuniv?iframe_url=/ArticleList.nhn%3Fsearch.clubid=30026525%26search.menuid=193%26search.boardtype=L 

코딩 커뮤니티 - 코뮤니티 [파이썬/... : 네이버 카페

문제 

카지노에서 자주 플레이되는 블랙잭의 규칙은 카드의 합이 21이 넘지 않는 한도 내에서, 카드의 합을 가장 크게 만드는 게임이다.

이와 유사하게, 코드메이트 버전의 블랙잭은 N개의 카드중 세장의 카드를 뽑아 X를 넘지 않으면서 X와 가장 가까운 수의 카드조합을 골라내는 규칙으로 진행된다.

​

첫째 줄에는 카드의 개수 N과 목표 값 X가 주어지며,

두번째 줄에는 카드에 쓰여있는 수가 입력으로 주어질 때,

X에 가장 가까우면서 X를 넘지 않는 카드 세장의 합을 구해서 출력하세요.

​

​

입/출력 예시

👉 입력 예시

5 21 1 2 3 4 5

👉 출력 예시

12

​

👉 입력 예시

8 100 16 85 30 14 95 63 52 87

👉 출력 예시

98

​

풀이

보너스 문제를 제외한 마지막 문제이다.

N의 최대 크기는 제한이 없고, 문제가 성립하려면 N은 항상 3이상이어야 한다.

주어진 카드들로 크기가 3인 조합을 재귀로 만들 수도 있고 3중 for문으로 만들 수도 있다.

본인은 간단하게 3중 for문으로 3개의 카드를 뽑는 모든 수를 검사하여 그 중 x를 넘지 않는 최댓값을 도출했다.

 

코드

#include <stdio.h>
#include <stdlib.h>

int main() {
	
	int n,x;
	// 3<=n<=?
	scanf("%d %d", &n, &x);
	//동적 배열
	int *arr = (int*)malloc(sizeof(int)*n);
	
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	int ans = 0;
	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 sum = arr[i] + arr[j] + arr[k];
				if (ans < sum && sum <= x) {
					ans = sum;
				}
			}
		}
	}
	if (ans ==0) {
		printf("답이 없음");
	}
	else {
		printf("%d", ans);
	}
	return 0;
}