[백준] 브루트포스

서론

---

브루트 포스 문제를 풀어보았다.

저번학기에 컴퓨터보안 시간에 브루트포스 공격을 하기 위한 프로그램을 자바로 만든적이 있었는데,

가능한 모든 경우의 비밀번호를 뚫기 위해 엄청 많은 시간이 든다는 것을 확인할 수 있었는데,

그래서 그런지 이번 단계는 시간 제한이 걱정되었지만, 시간 제한에 걸리진 않았다.

---

2798 : 블랙잭

---

문제

---

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

2798번: 블랙잭

 

이 문제는 3개의 수의 합이 주어진 수보다 작거나 같은 가장 큰 수를 찾는 문제이다.

---

해설

---

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int card[] = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(card);
        int sum = 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 tmp = card[i] + card[j] + card[k];
                    if(tmp <= M){
                        sum = Math.max(tmp, sum);
                    }
                }
            }
        }
        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
    }
}

N장의 카드를 입력받고 이를 배열에 저장한 후, 이를 정렬합니다.

정렬한 수들의 합이 M보다 작거나 같으면, 해당 값을 이전의 합과 비교하여 갱신합니다.

---

2231 : 분해합

---

문제

---

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

2231번: 분해합

자연수 N이 주어졌을 때, 생성자를 구해야 한다.

---

해설

---

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

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

        int N = Integer.parseInt(br.readLine());
        int res = 0;

        for (int i = 1; i <= N; i++) {
            String num = String.valueOf(i);
            int tmp = i;
            for (int j = 0; j < num.length(); j++) {
                tmp += Integer.parseInt(String.valueOf(num.charAt(j)));
            }
            if(N == tmp){
                res = i;
                break;
            }
        }
        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
    }
}

1부터 N까지의 수를 문자열에 넣고 이를 자기 자신 +  각 자리수별로 분해한 값을 계산한다.
(ex. 245 -> 245 + 2 + 4 + 5) 

더했을 때 N과 동일하다면, i가 생성자이다.

이때 가장 작은 생성자를 구하는 것이기 때문에, 1부터 시작하여 가장 먼저 찾아지는 생성자가 최소값이다.

따라서 break;를 통해 이후 반복문을 수행하지 않게 된다.

---

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

---

문제

---

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

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

이 문제는 연립방정식을 푸는 문제이다.

대입법을 프로그램으로 만들어서 풀어보려다가, 그냥 브루트포스라는 단계에 맞게 풀어보았다.

---

해설

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());

        StringBuilder sb = new StringBuilder();

        for (int i = -999; i <= 999; i++) {
            for (int j = -999; j <= 999; j++) {
                boolean res1 = (a * i + b * j) == c;
                boolean res2 = (d * i + e * j) == f;

                if(res1 && res2){
                    sb.append(i).append(" ").append(j);
                    break;
                }
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

연립방정식의 각 식에 i,j (x,y)를 대입해보고, 두 방정식을 모두 만족시키는 i,j(x,y)가 있을 때가 해당 방정식의 해이다.

---

1018 : 체스판 다시 칠하기

---

문제

---

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

1018번: 체스판 다시 칠하기

이 문제는 사실 생각을 좀 오래했던 문제이다.

NxM 체스판을 8x8로 분리하여, 패턴을 맞추기 위해 색을 변경해야 하는 횟수를 구하는 문제이다.

---

해설

---

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        char chess[][] = new char[N][M];

        for (int i = 0; i < N; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < M; j++) {
                chess[i][j] = tmp.charAt(j);
            }
        }

        char start = 'B';
        int cnt = 0;
        int res = 10000;
        for (int m = 0; m < 2; m++) {
            if(m == 0){
                start = 'B';
            }
            else {
                start = 'W';
            }
            for (int i = 0; i < N-7; i++) {
                for (int j = 0; j < M-7; j++) {
                    cnt = 0;
                    for (int k = 0; k < 8; k++) {
                        for (int l = 0; l < 8; l++) {
                            if(((k % 2 == 0 && l % 2 == 0) || (k % 2 != 0 && l % 2 != 0))
                                    && chess[i+k][j+l] != start){
                                cnt++;
                            }
                            else if(((k % 2 == 0 && l % 2 != 0) || (k % 2 != 0 && l % 2 == 0))
                                    && (chess[i+k][j+l] == start)){
                                cnt++;
                            }
                            else {
                                continue;
                            }
                        }
                    }
                    res = res > cnt ? cnt : res;
                }
            }
        }
        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
    }
}

먼저, 가장 변경 횟수가 적게 만들기 위해 체스판을 8 x 8크기로 분할하여 확인하기 위해서는

왼쪽 상단부터, 오른쪽 하단까지 한 칸씩 이동하며 확인을 해보아야 한다.

그러기 위해 4중 for문을 통해 더해줄 시작 인덱스 x,y 와 8 x 8의 체스판을 위한 0~7의 반복문을 통해 탐색한다.

그런데,  (0, 0)의 인덱스가 B이면, 행과 열이 모두 인덱스가 짝수인 경우에는 (0,0)과 같은 색으로 칠해져 있어야 한다.

또한, 행과 열 인덱스가 모두 홀수인 경우에도 마찬가지이다.

이와 반대의 경우에는 시작 인덱스(0,0)과 반대의 색으로 칠해져 있어야 한다.

위의 조건을 만족하지 못한다면, 바꿔서 칠해야하므로, 카운팅을 해주었다.

그리고, 시작 위치가 흰색, 검정색 두가지 경우가 다르기 때문에 두번 진행해주었다.

마지막으로, 반복문을 진행하며, 가장 작은 변경 횟수를 결과에 저장해준다.

---

1436 : 영화감독 숌

---

문제

---

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

1436번: 영화감독 숌

---

해설

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        String res = "666";
        int num = 0;

        while (N != 0) {
            num++;
            if(String.valueOf(num).contains(res)){
                N--;
            }
        }
        bw.write(String.valueOf(num));
        bw.flush();
        bw.close();
    }
}

0부터 시작해서 1씩 증가하는 수 num에 666이 포함되어 있다면, 이는 시리즈에 들어간 수이므로, N번째 수를 구하기 위해

조건을 만족할 때마다 N--를 해주고, N != 0이면, 그때의 num이 해당 시리즈에 들어갈 수이다.

---

2839 : 설탕 배달

---

문제

---

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

2839번: 설탕 배달

---

해설

---

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

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

        int N = Integer.parseInt(br.readLine());
        int res = -1;

        Loop:
        for (int i = N / 5; i >= 0; i--) {
            for (int j = 0; j <= N / 3 ; j++) {
                if((5 * i) + (3 * j) == N){
                    res = i + j;
                    break Loop;
                }
            }
        }
        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
    }
}

5kg 봉지를 많이 넣을 수록 개수가 줄어들기 때문에, 5kg 봉지가 최대로 들어갈 수 있는 개수부터 하나씩 줄여가며,

부족한 kg만큼 3kg 봉지로 채워주도록한다.

그렇게되면, 가장 먼저 5kg i개, 3kg j개를 더한 값이 N과 같을때 5kg 봉지가 가장 많을 것이므로, 개수는 최소가 된다.

---

결론

---

체스문제를 보았을 때 for문을 너무 많이 쓰는 것 같아서 다른 방법이 없을까 생각해보았는데, 없는 것 같다ㅠ.

뭔가 for문을 많이 써야하는 문제를 볼때마다, 제대로 된 풀이인지 너무 의심이 들어서 잘 생각해놓고도,

아닌 것 같다는 생각이 많이 들었는데, 나를 조금 더 믿어보도록 해야겠다.

---