[Algorithm] 백준 단계별로 풀어보기 - 단계 10. 브루트 포스

브루트 포스 알고리즘 응용

 

 

* 브루트 포스 알고리즘

가능한 모든 경우를 전부 만들어보는 알고리즘

 

2798. 블랙잭

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

public class BOJ_2798 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

		String[] input = rd.readLine().split(" ");
		int N = Integer.parseInt(input[0]);
		int M = Integer.parseInt(input[1]);
		
		//정수 배열로 저장
		int[] card = new int[N];
		String[] input2 = rd.readLine().split(" ");
		for(int i=0; i<N; i++) {
			card[i] = Integer.parseInt(input2[i]);
		}
		
		//오름차순 정렬
		Arrays.sort(card);
		int sum = 0, res = 0;
		for(int j=N-1; j>=2; j--) {
			for(int k=j-1; k>=1; k--) {
				for(int l=k-1; l>=0; l--) {
					sum = card[j]+card[k]+card[l];
					if(sum <= M) res = Math.max(sum, res);
				}
			}
		}
		
		System.out.println(res);
	}
}

입력받은 카드를 배열에 넣어 오름차순으로 정렬시켰다. 3개의 반복을 돌면서 큰 수부터 --하며 3개의 카드를 조합한다.

 

ex) 5 21 / 5 6 7 8 9 입력을 받은 경우

987, 986, 985 / 976, 975 ... 이렇게 큰 수부터 조합해주었다. 이 경우에는 21(975 조합)이 최대값이다.

3개의 카드(card[j], card[k], card[l])를 더해서 sum에 저장한 다음, 전에 있는 수보다 큰 경우에만 res에 넣어주고 최종적으로 res를 출력해주면 된다.

 

2231. 분해합

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_2231 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		String N = rd.readLine();
		int N2 = Integer.parseInt(N);
		
		String str;
		int hap;
		boolean flag = true;
		
		for(int i=1; i<=N2; i++) {
			hap = i;
			str = Integer.toString(i);
			for(int j=0; j<str.length(); j++) {
				hap += str.charAt(j)-48;
			}
			if(hap==N2) {
				System.out.println(i);
				flag = false; break;
			}
		}
		if(flag) System.out.println("0");
	}
}

str.charAt(j)-48를 사용하여 문자를 각 자리 숫자로 바꾸어 주었음.

생성자는 입력받은 수 N보다 클 수 없으므로 1부터 N까지 반복시켰다. N과 각 자리수를 더한 값이 N과 같아졌을 때 break하고 출력.

 

7568. 덩치

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_7568 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(rd.readLine());
		
		int arrX[] = new int[N];
		int arrY[] = new int[N];
		
		for(int i=0; i<N; i++) {
			String input[] = rd.readLine().split(" ");
			arrX[i] = Integer.parseInt(input[0]);
			arrY[i] = Integer.parseInt(input[1]);
		}
		
		int ranking;
		for(int j=0; j<N; j++) {
			ranking = 1;
			for(int k=0; k<N; k++) { //모든 사람을 전부 검사하기
				if(arrX[j]<arrX[k] && arrY[j]<arrY[k])
					ranking++;
			}
			System.out.print(ranking+" ");
		}
	}
}

 

1018. 체스판 다시 칠하기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class BOJ_1018 {
	static char[][] whiteChess = new char[][] {
		{'W','B','W','B','W','B','W','B'},
		{'B','W','B','W','B','W','B','W'},
		{'W','B','W','B','W','B','W','B'},
		{'B','W','B','W','B','W','B','W'},
		{'W','B','W','B','W','B','W','B'},
		{'B','W','B','W','B','W','B','W'},
		{'W','B','W','B','W','B','W','B'},
		{'B','W','B','W','B','W','B','W'}
	};
	static char[][] blackChess = new char[][] {
		{'B','W','B','W','B','W','B','W'},
		{'W','B','W','B','W','B','W','B'},
		{'B','W','B','W','B','W','B','W'},
		{'W','B','W','B','W','B','W','B'},
		{'B','W','B','W','B','W','B','W'},
		{'W','B','W','B','W','B','W','B'},
		{'B','W','B','W','B','W','B','W'},
		{'W','B','W','B','W','B','W','B'}
	};
	
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		String XY[] = rd.readLine().split(" ");
		int X = Integer.parseInt(XY[1]);
		int Y = Integer.parseInt(XY[0]);
		
		//2차원 배열에 넣기
		char array[][] = new char[X][Y];
		for(int y=0; y<Y; y++) {
			String input =  rd.readLine();
			for(int x=0; x<X; x++) {
				array[x][y] = input.charAt(x);
			}
		}
		
		int indexX = X-7, indexY = Y-7;
		int res1 = getDif(array, whiteChess, indexX, indexY);
		int res2 = getDif(array, blackChess, indexX, indexY);

		System.out.println(Math.min(res1, res2));
	}
	
	public static int getDif(char[][] array, char[][] targetChess, int indexX, int indexY) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		int dif = 0;
		for(int i=0; i<indexY; i++) {
			for(int j=0; j<indexX; j++) {
				dif = 0;
				for(int m=0; m<8; m++) {
					for(int n=0; n<8; n++) {
						//비교하기
						if(targetChess[n][m] != array[n+j][m+i])
							dif++;
					}
				}
				result.add(dif);
			}
		}
		Collections.sort(result);
		
		return result.get(0);
	}
}

[입력]

10 13

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

WWWWWWWWWWBWB

WWWWWWWWWWBWB

 

입력이 위와 같을 때 10, 13 크기의 배열 안에서 총 18개의 8x8 체스판이 나올 수 있다.

Black, White로 시작하는 8x8 배열을 초기화 해주고, 18개의 체스판을 초기화한 배열과 비교하며 다른 경우 dif를 증가해주었다.

최종적인 dif는 ArrayList에 추가해주고, 가장 작은 값을 출력시켰다. 모든 경우를 고려해서 풀었음.

 

+) Black으로 시작할 경우와 White로 시작할 경우 두 가지를 모두 고려해주어야 한다.

어떤 색을 바꾸는 것이 더 적게 체스판을 칠하는 것인지 모르기 때문!