[JAVA] 브루트 포스

브루트 포스란?

• 모든 경우의 수를 돌려보는...무식하지만 확실한 방법이다.

---

2798 블랙잭

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


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 n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine(), " ");
    int num[] = new int[n];
    for (int i=0;i<n;i++) num[i]=Integer.parseInt(st.nextToken());

    int max=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++){
          if (num[i]+num[j]+num[k]> max && num[i]+num[j]+num[k]<=m) max = num[i]+num[j]+num[k];
        }
        
      }
    }

    System.out.println(max);

    br.close();
    

  }
}

3중 반복문을 사용했다. 이때 첫번째 반복과 두번째 반복은 각각 n-2, n-1까지만 반복하는 것이 중요하다.

 

---

2231 분해합

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


    int num = Integer.parseInt(br.readLine());
    int i=0;

    for (i=0;i<num;i++){
      String str = Integer.toString(i);
      int sum=i;

      for (int j=0;j<str.length();j++){
        char c = str.charAt(j);
        int n = Character.getNumericValue(c);
        sum +=n;
      }

      if (sum==num) {
        System.out.println(i);
        break;
      }

    }

    if (i==num) System.out.println(0);



  }
}

Char형을 int형으로 바꾸기 위해서는 Character.getNumericValue() 메서드를 이용한다.

바로 sum에다가 합치면 안되고 int형 변수에 한번 저장한 후 더할 수 있다. 안그러면 오류가 난다...

 

---

19532 수학은 비대면강의입니다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


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 a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());
    int d = Integer.parseInt(st.nextToken());
    int e = Integer.parseInt(st.nextToken());
    int f = Integer.parseInt(st.nextToken());

    for (int i = -999; i <= 999; i++){
      for (int j = -999; j <= 999; j++){
        if (a*i + b*j == c && d*i + e*j == f){
          System.out.println(i + " " + j);
          break;
        }
      }
    }

    br.close();

  }
}

 

---

1018 체스판 다시 칠하기

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {

  public static boolean[][] arr;
  public static int min = 64;

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    arr = new boolean[N][M];


    // 배열 입력 
    for (int i = 0; i < N; i++) {
      String str = br.readLine();

      for (int j = 0; j < M; j++) {
        if (str.charAt(j) == 'W') {
          arr[i][j] = true;		// W일 때는 true 
        } else {
          arr[i][j] = false;		// B일 때는 false
        }

      }
    }


    int N_row = N - 7;
    int M_col = M - 7;

    for (int i = 0; i < N_row; i++) {
      for (int j = 0; j < M_col; j++) {
        find(i, j);
      }
    }
    System.out.println(min);
  }


  public static void find(int x, int y) {
    int end_x = x + 8;
    int end_y = y + 8;
    int count = 0;

    boolean TF = arr[x][y];	// 첫 번째 칸의 색 

    for (int i = x; i < end_x; i++) {
      for (int j = y; j < end_y; j++) {

        // 올바른 색이 아닐경우 count 1 증가 
        if (arr[i][j] != TF) {	
          count++;
        }

        /* 
         * 다음 칸은 색이 바뀌므로
         * true라면 false로, false 라면 true 로
         * 값을 변경한다.
         */
        TF = (!TF);
      }

      TF = !TF;
    }

    /*
     *  첫 번째 칸을 기준으로 할 때의 색칠 할 개수(count)와
     *  첫 번째 칸의 색의 반대되는 색을 기준으로 할 때의
     *  색칠 할 개수(64 - count) 중 최솟값을 count 에 저장 
     */
    count = Math.min(count, 64 - count);

    /*
     * 이전까지의 경우 중 최솟값보다 현재 count 값이
     * 더 작을 경우 최솟값을 갱신 
     */
    min = Math.min(min, count);
  }
}

이건 진짜 너무 어려워서 해설이 필요하다...

일단 최소 체스판 크기가 8X8이므로 (가로칸-7)x(가로칸-7)만큼 count를 비교하는 경우의 수가 있고, 

첫번째 칸이 흰색 혹은 검은색이냐에 따라서(풀이에서는 T/F로 구분했다.)도 비교를 해야하므로 2X8X8만큼 비교해야 한다.

 

---

1436 영화감독 숌

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int count = 1;
    int i=665;

    while (true){
      String str = Integer.toString(i);
      if (str.contains("666")){
        if (count==n) break;
        else count++;
      } 
      
      i++;
    }
    
    System.out.println(i);
  
  }
}

 

---

2839 설탕배달

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
//import java.util.Arrays;


public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int i=0;
    int j=0;

    loop:
    for (i=0; i<n; i++){
      for (j=0; j<n; j++){
        if (j*5 + i*3 == n){
          System.out.println(i+j);
          break loop;
        }
      }
    }

    if (i==n) System.out.println(-1);
  
  }
}

이중 for문에서 그냥 break;만 하게 된다면 가장 안쪽 반복문만 빠져나오게 된다.

그럴 때는 for문에 loop:와 같이 이름을 붙여서 특정 loop를 빠져나오게 할 수 있다.

물론 for문이 여러개일 때 각 for문에 이름을 모두 붙여서 break를 조절할 수 있다.

 

---

# 회고

 

브루트포스는 무식해서 좀 그렇지만 간단해서 좋다.

가끔은 복잡하게 하는 것보다 브루트포스가 더 좋을 수도...