21.08.12 기록

백준 알고리즘 2798 풀이

🎆나의 풀이(메모리 14.2MB, 시간 140ms로 통과)

브루트 포스 알고리즘 (Brute force search) 🌴Reference

• 완전 탐색 알고리즘이다.
• 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

-모든 경우의 수를 따져보면 되므로, for문 3개를 사용하여 M보다 작거나 같은 수중 최댓값을 출력했다.

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

  public class B2798 {

      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");

          int[] numbers = new int[Integer.parseInt(st.nextToken())];
          int M = Integer.parseInt(st.nextToken());

          st = new StringTokenizer(br.readLine(), " ");
          for(int i = 0; i < numbers.length; i++) {
              numbers[i] = Integer.parseInt(st.nextToken());
          }

          System.out.println(search(numbers, M));
      }

      public static int search(int[] numbers, int M) {
          int max = 0;
          for(int i = 0; i < numbers.length-2; i++) {
              for(int j = (i+1); j < numbers.length-1; j++) {
                  for(int k = (j+1); k < numbers.length; k++) {
                      int sum = (numbers[i] + numbers[j] + numbers[k]);

                      if(sum == M) { return sum; }
                      if(sum < M && max < sum) { max = sum; }
                  }
              }
          }
          return max;
      }
  }

🎆해설(메모리 14.1MB, 시간 132ms로 통과)

-아래 코드는 조건문을 추가하여 불필요한 탐색을 줄이는 방법이다.
-요소의 값이 M보다 크다면 추가 탐색을 할 필요가 없으므로 이를 조건문으로 활용한다.

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

  public class B2798 {

      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");

          int[] numbers = new int[Integer.parseInt(st.nextToken())];
          int M = Integer.parseInt(st.nextToken());

          st = new StringTokenizer(br.readLine(), " ");
          for (int i = 0; i < numbers.length; i++) {
              numbers[i] = Integer.parseInt(st.nextToken());
          }

          System.out.println(search(numbers, M));
      }

      public static int search(int[] numbers, int M) {
          int max = 0;
          for (int i = 0; i < numbers.length - 2; i++) {
              if(numbers[i] > M) { continue; }

              for (int j = (i + 1); j < numbers.length - 1; j++) {
                  if(numbers[i] + numbers[j] > M) { continue; }

                  for (int k = (j + 1); k < numbers.length; k++) {
                      int sum = (numbers[i] + numbers[j] + numbers[k]);
                      
                      if (sum == M) { return sum; }
                      if (sum <= M && max < sum) { max = sum; }
                  }
              }
          }
          return max;
      }
  }