2798번 문제 : 블랙잭

2798번: 블랙잭 (acmicpc.net)

2798번: 블랙잭

 

후 알고리즘 생각해 내기가 어려웠다.

혜원이가 도와줘서 계산기 열심히 뚜드려가면서 알고리즘을 짰다

1. 배열 정렬

2. 제일 큰 수를 max로 잡고 그 수 보다 인덱스 -1인 값을 중간값으로 잡는다.

  그 수가 500을 넘으면 두 번째 수 잘못 잡은 거니까 continue

  500을 넘지 않으면 제일 작은수 (k=0) arr[k]를 더해봐서 500이 넘으면 두 번째값 잘못됐으니까 continue

                                                              500이 넘지 않으면 list에 총 다 더한 값을 넣고 k++해서 그 다음 작은 수를 더해봐

3. 두 번째 값을 배열안에서 다 돌면

   제일 큰 수 인덱스를 -1하고 다시 반복.

이 전체과정은 int max = arr[arr.length-m]; 에서 m != arr.length -1 조건 만족할 때까지 이 말은 max값이 최소 값 인덱스 3번째까지 반복하기 위함.

 

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				
		StringTokenizer st = new StringTokenizer(br.readLine());
		int num = Integer.parseInt(st.nextToken());
		int key = Integer.parseInt(st.nextToken());
		int sum = 0;
		int arr[] = new int[num];
		List <Integer> list = new ArrayList<>();
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<num;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		
		int m=1;
		int k=0;
		while(m != arr.length-1) {
			int max = arr[arr.length-m];//제일 큰 수

			for(int i=m+1;i<arr.length;i++) {
				sum = max + arr[arr.length-i];
				
				if(sum >= key) {//제일 큰 수 두 개를 잡았을 때 key값과 같거나 넘어버리면
					continue;
				}
				else { //큰 수 두 개를 잡았을 때 key값보다 작으면
					k=0;
					while(sum+arr[k] <= key && arr[arr.length-i] != arr[k]) { //제일 작은 수부터 구해봄
						list.add(sum+arr[k]);
						k++; //제일 작은 수를 증가시켜봄
					}
				}
			}
			m++; //제일 큰 수를 그 다음 번 째 큰 수로 조정
		}
		Collections.sort(list,Collections.reverseOrder());
		System.out.println(list.get(0));
	}
}

후 ㅋ 혜원아 고마워

 

근데 완전탐색, 브루트 포스 알고리즘을 써야한단다...........

완전탐색, 브루트 포스란 모든 경우의 수를 시도해보는 방법이래 근데 나도 ㅇ모든 경우의 수를 시도했는데 ?????