백준 2798: 블랙잭(java/C)

문제

 

풀이

3중 for문을 사용하여(카드 3장을 고르므로 3중, n장 뽑으려면 n중첩) N개의 카드에서 가능한 모든 경우의 수를 탐색하면 된다. 전체 탐색을 하려니 N이 커질수록 너무 비효율적일 것 같았지만... 고민해 봐도 다른 방법은 잘 모르겠다ㅜ

 

1. 전체 경우의 수를 탐색하고

2. 이들 중 합이 M에 가장 가까운 것을 출력

 

하는 간단한 알고리즘이다.

 

[JAVA]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st=new StringTokenizer(in.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		
		st=new StringTokenizer(in.readLine());
		int[] cardArr=new int[N];
		for(int i=0; i<N; i++) 
			cardArr[i]=Integer.parseInt(st.nextToken());
		
		int sum=0;
		int result=0;
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				for(int k=j+1; k<N; k++){
					sum=cardArr[i]+cardArr[j]+cardArr[k];
					if(sum>result&&sum<=M)
						result=sum;
				}
			}
		}
		System.out.println(result);
	}
}

result는 지금까지 계산한 것 중 M에 가장 가까운 sum을 저장하는 변수이다. 루프를 돌며 더 적합한 sum이 나오면 갱신된다.

 

[C]

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main(void) {
	int N, M;
	scanf("%d %d", &N, &M);

	int* cardArr = (int*)malloc(N * sizeof(int));
	for (int i = 0; i < N; i++)
		scanf("%d", &cardArr[i]);

	int sum = 0;
	int result = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			for (int k = j + 1; k < N; k++) {
				sum = cardArr[i] + cardArr[j] + cardArr[k];
				if (sum > result && sum <= M)
					result = sum;
			}
		}
	}
	printf("%d", result);

	return 0;
}