브루트 포스는 완전탐색 즉 모든 경우의 수를 탐색하는 알고리즘이다.
01. 2309번 - 일곱 난쟁이
9명의 난쟁이의 키가 주어질때, 이중 7개의 난쟁이의 키의 합이 100인경우를 아무거나 오름차순으로 출력한다.
7명의 난쟁이를 고르라고 했으니, 2명의 난쟁이를 제외하면 된다는 생각을 할 수있다. 전체 입력받은 9명의 난쟁이의 키를 합한 total을 구한다. 이후 이 total값에서 2명의 난쟁이의 키를 전부 빼본다. 브루트 포스로 풀수 있는 이유는 2명의 난쟁이를 선택하는 경우의 수가 9C2 9*8/2 = 36가지의 경우의 수밖에 없기 때문이다.
하나씩 해볼때마다, 2명의 난쟁이의 키 값을 뺀 total값이 100과 같으면 출력후 return 한다.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int height[9];
int total =0;
int first=0; int second=0;
for(int i=0; i<9; i++){
cin>>height[i]; //키를 입력받음.
total+=height[i];
}
for(int i=0; i<8; i++){
int cal = total;
cal -=height[i];
for(int j=i+1; j<9; j++){
cal -=height[j];
if(cal==100){
first = height[i];
second = height[j];
sort(height, height+9); //정렬
for(int k=0; k<9; k++){
if(height[k]!=first && height[k]!=second){
cout<<height[k]<<'\n';
}
}
return 0;
}else{
cal +=height[j]; //다시 원래상태로
}
}
}
return 0;
}애초에 정렬을 한후에 제외할 애를 선택했다면, first/second와 같은 변수를 둘 필요 없이 i, j값으로 처리할 수 있을것이다.
02. 3085번 - 사탕게임
이번에도 마찬가지로 브루트 포스를 이용하여 풀 수 있다. 사탕을 한번 swap하고, 전체 판을 탐색해서 가장 긴 연속의 수를 찾는다. 이것을 max로 두고 최종적으로 가장긴 max를 찾는다.
모든 위치의 사탕을 swap한다. 예를 들어 [i][j]번째 위치의 사탕이 있을때, swap을 하는 방법은 2가지인데, [i][j+1]인 오른쪽의 위치와 swap을 하는경우, [i+1][j] 로 아래쪽에 위치하는 사탕과 swap을 하는 경우이다. 위와 왼쪽은 생각하지않는 이유는, 위의 사탕이 아래쪽(현재)의 사탕과 swap == 현재위치 위쪽의 사탕과 swap 이기 때문이다.
하나의 사탕을 swap 한후 가장긴 연속수를 컬러의 길이를 찾고 return 하는 method를 함수를 만든다. 그리고 swap했던거 원래 제위치로 다시 swap.
이 문제 또한 브루트포스로 풀수있는 이유는 n이 최대 50이기때문이다. 50개의 바둑판을 전부 swap하는 경우의 수는 50*50 이고 각 swap하는 경우에 전체 바둑판을 또 뒤지기때문에 50*50의 시간복잡도가 걸린다. 따라서 50의 4승 50의 4승은 2500의 2승이고 이것은 1억(=1초)에 미치지 못하기때문에 브루트포스로 풀이가 가능하다.
#include <iostream>
#include <algorithm>
using namespace std;
char arr[50][50];
int n;
int find_longest(){
int max =0;
for(int i=0; i<n; i++){
int cnt =1;
for(int j=0; j<n-1; j++){ //행의 연속을 체크
if(arr[i][j]==arr[i][j+1]){
cnt++;
}else{
if(cnt>max)
max = cnt;
cnt =1;
}
}
if(cnt>max){
max = cnt;
}
cnt =1;
for(int j=0; j<n-1; j++){ //열의 연속을 체크
if(arr[j][i]==arr[j+1][i]){
cnt++;
}else{
if(cnt>max){
max =cnt;
}
cnt=1;
}
}
if(cnt>max){
max = cnt;
}
}
return max;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int answer =0;
cin>>n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin>>arr[i][j];
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int result=0;
if(j+1<n){
//1.오른쪽이랑 swap
swap(arr[i][j],arr[i][j+1]);
result = find_longest();
if(result>answer){
answer = result;
}
swap(arr[i][j],arr[i][j+1]); //원상복귀
}
//2.아래쪽이랑 swap
if(i+1<n){
swap(arr[i][j],arr[i+1][j]);
result=find_longest();
if(result >answer)
answer = result;
swap(arr[i][j],arr[i+1][j]);
}
}
}
cout<<answer;
return 0;
}
03. 1476번 - 날짜계산
이문제는 반복문을 이용하여 cnt를 증가시켜서 입력받은 ESM과 같은 경우를 찾거나, 나머지 연산을 이용해 푸는 방법이 있다.
cnt를 증가시키는 경우에는, while문을 돌리면서, E의 최대값 15를 넘어선 16이 됐을때, e를 1로 돌려준다. S와 M도 마찬가지다. 이렇게 계속 증가시키고 난후, 입력받은 ESM과 계산하는 값인 esm이 같은경우에 break한다.
브루트 포스로 풀수있는 경우 최대 15 * 28 * 19 의 경우의 수가 나오므로 1억에 비해 상대적으로 굉장히 작은수 이기 때문.
#include <iostream>
using namespace std;
int main()
{
int E,S,M;
int e=1;
int s=1;
int m=1;
int result =1;
cin>>E>>S>>M;
while(true){
if(e==E && s==S && m==M){
break;
}
e++; s++; m++; result++;
if(e>15){
e=1;
}
if(s>28){
s=1;
}
if(m>19){
m=1;
}
}
cout<<result;
return 0;
}
04. 1107번 - 리모컨
이 문제는 코드를 이해하는것이 조금 헷갈렸다. 아무래도 조건문이 많고 예외처리, 혹은 잔계산이 조금 있기 때문인것같다.
이문제 또한 브루트 포스로 풀수 있는 이유는, 이동하려고하는 채널이 최대 50만이기 때문이다. 채널의 개수는 무한대이지만 이동하려는 채널은 50만개라는 말은 예를 들어 500,000번 채널로 이동하려고할때, 500,001번 채널을 숫자로 이동후 - 버튼을 눌러 최종 이동가능하다는 것이다. 때문에, 숫자로 클릭할 수있는 최대 이동 채널은 500,000의 두배인 대략 100만이다. 이유는 0 -> 50만 <- 100만 의 이동횟수는 같기 때문에..
예외처리를 해야하는 부분은, 현재 채널은 100인데, 101로 가는경우, 100으로 가는경우가 있다고생각해보자. 전자는 1,0,1, 숫자를 3개눌러 가는 경우보다 +를 한번눌러 가는경우가 더 최소클릭횟수이다. 100또한 1,0,0 3번 눌러가는 경우보다 그냥 가만히있는 0이 최소클릭횟수이다. 때문에 +로 가는 이동횟수 n-100을 구한다 ( 음수일수도있으니 절대값 처리를 해준다)
그리고 1~1,000,000 까지의 채널을 돌면서 버튼이 고장나서 못가는 경우와 갈수있는 경우를 찾는다. 갈수있다면 그 채널에서부터 최종목표 N까지가는데 -- 혹은 ++를 몇번 눌러야하는지 체크한다. 채널을 이동하는 횟수는 채널의 숫자의 개수이고 ++ /--를 눌러야하는 수는 최종 N - 채널숫자이다. (이것또한 절대값 처리를해준다.) 이중 값이 가장 적은 ans가 최종 답이된다.
#include <iostream>
using namespace std;
bool buttons[10]; //false 사용가능 true 사용불가능(고장)
int possible(int c){
if(c==0){
if(buttons[c]){
return 0; // 0사용불가능
}else{
return 1; // 1자리 눌러라
}
}
int len =0;
while(c>0){
if(buttons[c%10]){
return 0; //불가능하면 0 return
}else{
len++;
}
c /= 10;
}
return len; //자리수 return
}
int main()
{
int n;
int b_num;
cin>>n>>b_num;
for(int i=0; i<b_num; i++){
int x;
cin>>x;
buttons[x] = true; // 고장나면 true
}
//1. 그냥 지금위치 100에서 ++혹은 --만해서 채널이동
int ans = n-100;
if(ans<0){ // 100보다 작은 채널일때
ans = -ans;
}
for(int i=0; i<1000000; i++){ //전체 모든 100만까지의 채널에서 숫자+ ++/--
int c = i; //채널 c
int result = possible(c); //채널이동 가능??
if(result>0){ //다 숫자버튼눌러서 이동가능한 채널일때만.
int push_pn = n-c; //++ or --를 눌러야하는 횟수
if(push_pn<0){
push_pn = -push_pn; //절대값 취해주고
}
if(ans>push_pn+result){
ans = push_pn+result;
}
}
}
cout<<ans;
return 0;
}
05. 14500번 - 테트로미노★ - ( 최종해결 x )
이 문제 또한 모든 블럭 (19가지)을 바둑판에 넣어보고 최대값을 도출하는 문제이다. 도형이 대칭 회전이 가능하므로, 5개의 도형이 주어졌지만, 19가지의 모양이 가능하다.
전체 바둑판을 돌며 i , j 값을 변경해주어야한다. 나는 각각의 도형마다 i , j값을 제한을 두고 for문을 돌렸는데, 이것보단 n, m 까지 전체 for문을 돌리며, 안에서 조건문으로 제한하는것이 훨씬 효과적인 방법인것같다.
'알고리즘' 카테고리의 다른 글
| BOJ 백준 15831 준표의 조약돌 (0) | 2019.12.30 |
|---|---|
| BOJ 백준 6064, 1748 (0) | 2019.12.19 |
| C++ // Method 정리 (0) | 2019.12.18 |
| BOJ 백준 1463, 11726, 11727, 9095 (0) | 2019.11.29 |
| 04 다이나믹프로그래밍 (DP) (0) | 2019.11.21 |