코딩테스트/백준

[백준 JAVA] 2798 - 블랙잭

kittae 2024. 12. 5. 20:16

매우 쉬운 문제다!

3년 전에 알고리즘을 모르고 단순히 반복분과 중첩문만을 가지고 문제를 풀었던 시절이 있었다.

 

그때는 c++로 했었는데 티어가 높아질 수 록 매 문제마다 시간 초과 문제가 생겼던 기억이 난다.

 

지금 다시 확인해 보니깐, 내가 풀었던 알고리즘은 실제로 있는 브루트포스란 알고리즘이었다!! (말 그대로 무식한 힘) 

 

시간 복잡도는 N이 100이라는 점에서 시간 제한과 메모리 제한은 여유롭다고 판단했다!

 

구현 로직

for (int i = 0; i < n; i++)
	for (int j = i+1; j < n; i++)
    	for (int k = j+1; k < n; k++)
        
        	if (arr[i] + arr[j] + arr[k] <= 21보다 작아야됨 && 해당 더한 값이 max보다 크면?)
            	max = arr[i] + arr[j] + arr[k]

 

 

[최종코드]

import java.io.*;
import java.util.*;

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(), " ");
        ArrayList<Integer> arr = new ArrayList<>();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {

            arr.add(Integer.parseInt(st.nextToken()));
        }

        int max = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {

                    int sum = (arr.get(i) + arr.get(j) + arr.get(k));

                    if (sum <= m && max <= sum)
                        max = sum;
                }
            }
        }

        System.out.println(max);
    }
}