[Java] 백준 bruteforcing - 브론즈

 

브루트포스로 문제를 풀어야만 하는 경우에 다른 방법을 시도하다 시간을 낭비한 적이 많다. 아직 브루트포스 방식에 익숙하지 않기 때문이라고 생각한다. 그래서 해당 풀이법과 관련있는 문제들을 많이 풀어보려고 한다.!

 

 

브루트 포스(bruteforcing)

• brute: 짐승 같은, 난폭한
• brute-force: (정제되지 않은) 난폭한 힘, 폭력
• 이론적으로 가능한 모든 경우의 수를 찾아보는 방법
• 시간과 자원이 많이 드는 무식한 방법
• 가장 확실하면서 정확도 100%를 보장함

 

 

1837 암호제작 브론즈3

https://www.acmicpc.net/problem/1837

1837번: 암호제작

 

풀이법 생각

• K보다 작은 소수들을 모두 P에 나눠봄
  • 만약 나눠진다? K보다 작은 소수가 암호제작에 사용되었다는 거니까 BAD를 출력
  • 안나눠지면 포함 안된거니까 GOOD (일단 소수 2개로 만든건 분명하니까)
• 소수 구하는 법은 다음이 있는데 전자가 더 좋은 것 같음
  1. 1부터 시작해서 배수를 삭삭 지워주는 방법
  2. sqrt(i) 까지 다 나눠보는 방법

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
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());
    BigInteger password = new BigInteger(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    boolean[] isNotPrime = new boolean[k+1];
    isNotPrime[1] = true;

    for (int i=2; i<k; i++) {
      if (isNotPrime[i])
        continue;

      if (password.mod(BigInteger.valueOf(i)).compareTo(BigInteger.ZERO) == 0) {//나머지 0이면
        System.out.println("BAD " + i);
        return;
      }

      //소수인데 소수인 쌍이 없샴
      for (int j = 2*i; j<=k; j+= i) {
        isNotPrime[j] = true;
      }
    }

    System.out.println("GOOD");
  }
}

• 소수가 아닌 애들을 모아두는 배열을 k+1크기로 만들어줌 (1부터 세고 0은 사용안하려는 전략)
• 소수라면 P에 나눠줌 -> 나누어 떨어진다면 해당 소수를 사용하여 암호를 만든거니까 BAD출력
  • 나눈 몫이 소수인지는 알 필요 없음
  • 어차피 소수끼리의 곱이니까 나누어떨어지기만 한다면 다른 경우는 없는 것!

 

주의점

• BigInteger로 안해줘서 NumberFormatException 이 계속 발생했음
• BigInteger는 나머지 연산자도 안되고, 나누기도 다 안되고, 비교하는 것도 까다로워서 좀 힘들었다
• 다음 블로그를 많이 참고했당
  • https://umilove98.tistory.com/73

 

 

2798 블랙잭 브론즈2

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 br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int cardCnt = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int result = 0;

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

    int[] arr = new int[cardCnt];

    for (int c =0; c<cardCnt; c++)
      arr[c] = Integer.parseInt(st.nextToken());

    for (int i =0; i<cardCnt-2; i++) {
      int cal1 = arr[i];

      if (cal1 > M) continue;

      for (int j = i+1; j<cardCnt-1; j++) {
        int cal2 = cal1 + arr[j];

        if (cal2 > M) continue;

        for (int z = j+1; z<cardCnt; z++) {
          int cal3 = cal2 + arr[z];

          if (cal3 > M) continue;

          //이 뒤로는 볼 필요도 없음
          if (cal3 == M) {
            System.out.println(cal3);
            return;
          }

          //갱신
          if (result < cal3)
            result = cal3;
        }
      }
    }

    System.out.println(result);
  }
}

• 정말 하나하나 다 대입해보는 방법
• 조금이라도 시간을 줄이기 위해 중간에 M보다 큰지 확인하는 if문을 넣어줌

 

2309 일곱 난쟁이 브론즈1

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

public class Main {

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

    int sum = 0;
    for (int i =0; i<9; i++) {
      int h = Integer.parseInt(br.readLine());
      height[i] = h;
      sum += h;
    }

    boolean found = false;
    for (int i =0; i<8; i++) {
      for (int j =i+1; j<9; j++) {
        if (sum - height[i] - height[j] == 100) {
          height[i] = 0;
          height[j] = 0;
          found = true;
          break;
        }
      }

      if (found)
        break;
    }

    Arrays.sort(height);

    for (int i =2; i<9; i++)
      System.out.println(height[i]);

  }
}

• 아홉 난쟁이 중에 일곱 난쟁이의 키를 더하는 것보다 난쟁이 둘을 빼는게 더 효율적이라고 생각함
  • 이중 for문으로 해결이 가능
• 키가 100이 될 때까지 난쟁이 키의 합에서 두 난쟁이씩 빼줌

 

 

 

 

브루투포스 방법은 단순 계산이라 어렵지 않기때문에 브론즈문제는 3개로 충분할 것 같다. 

(수학계산으로 풀겠다고 삽질만 하지 않으면 전혀 어렵지 않음)

실버도 굉장히 쉬운편이라서 바로 실버, 골드로 넘어가야겠당