[코딩테스트] 브루트 포스2
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
날짜 계산(1476번)
https://www.acmicpc.net/problem/1476
문제
준규가 사는 나라는 E S M 이라는 연도를 사용. 1≤E≤15, 1≤S≤28, 1≤M≤19.
1년 = 1 1 1, 2년 = 2 2 2, … , 15년 = 15 15 15, 16년 = 1 16 16 , 17년 = 2 17 17, 18년 = 3 18 18, 19년 = 4 19 19, 20년 = 5 20 1, 21년 = 6 21 2
E S M 이 주어졌을 때, 몇 년인지 구하는 문제이다.
입력
첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.
출력
첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.
풀이
-
조합의 수 : 15x28x19 = 7980, 따라서 브루트포스 적합
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int E = sc.nextInt(); int S = sc.nextInt(); int M = sc.nextInt(); int e = 1, s = 1, m = 1; for (int i = 1;; i++) { if (E == e && S == s && M == m) { System.out.println(i); break; } e += 1; s += 1; m += 1; if (e == 16) { e = 1; } if (s == 29) { s = 1; } if (m == 20) { m = 1; } } } } -
더 수학적인 방법 : 모든 E,S,M에서 1을 빼면 이 문제는 다음을 만족하는 가장 작은 자연수 year를 찾는 문제이다. (year-1 해서 구하고 출력할때 year+1)
- 1≤E≤15 = 0≤E ＜ 15 = E는 15로 나눈 나머지
- year mod 15 == E
- year mod 28 == S
- year mod 19 == M
- 이런식으로 year를 0부터 증가시키며 위의 식을 검사해 구현하는 방법
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int e = sc.nextInt() - 1; int s = sc.nextInt() - 1; int m = sc.nextInt() - 1; for (int i = 0;; i++) { if (i % 15 == e && i % 28 == s && i % 19 == m) { System.out.println(i + 1); break; } } } } -
중국인의 나머지 정리로도 풀 수 있다.
리모컨(1107번)
https://www.acmicpc.net/problem/1107
문제
TV 채널을 리몬컨을 이용해 바꾸는 문제, 버튼 : 0,1,2,3,4,5,6,7,8,9,+,-
일부 숫자 버튼이 고장남. 현재 보고 있는 채널 : 100, 이동하려 하는 채널 : N
이 때 리모컨 버튼을 누르는 횟수를 최소로 하는 문제
입력
첫째 줄에 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000). 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10). 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
풀이
- 불필요한 값, 중복되는 값을 제거. 최소값.
- 숫자 버튼(0~9) -> +/- 버튼 순서
- +/- 버튼 둘 중에 하나만
- ① 숫자 버튼을 이용해 어디로 이동할지? (알 수 없다. 따라서 브루트포스 방법을 이용한다.)
② +/- 몇 번 눌러야 하는지? - 이동하려고 하는 채널 N(0 ≤ N ≤ 500,000) 이지만 숫자 버튼을 눌러 이동하는 채널 C도 (0 ≤ N ≤ 500,000) 여선 안 된다.
- 500,000 이동 / 1,5만 누를 수 있는 경우 15,555->500,000보다 511,111->500,000이 더 좋음.
- 모든 숫자가 고장났음. 100번 -> 500,000번일 땐 50만번 최대값 / -를 50만번 누르는 곳은 100만번. 따라서 0 ≤ C ≤ 1,000,000
- 이동할 채널 C를 정한다.
- C에 포함되어 있는 숫자 중에 고장난 버튼이 있는지 확인한다(반복문) or 고장나지 않은 버튼을 이용해 이동할 수 있는 채널 C를 만든다(재귀함수) // 시간복잡도가 같으면 편한 방법을 택하기
-
고장난 버튼이 포함되어 있지 않다면 C-N 을 계산해 +나 -버튼을 몇 번 눌러야 하는지 계산한다. - 숫자 버튼을 누르지 않는 경우도 계산 = 정답의 초기값
import java.util.*;
public class Main {
static boolean[] broken = new boolean[10];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 채널 N
int m = sc.nextInt(); // 고장난 버튼 갯수
int btn[] = new int[n];
for (int i = 0; i < m; i++) {
int x = sc.nextInt();
broken[x] = true; // 고장난 버튼 true로 바꾸기
}
int ans = n - 100; // 숫자 안 누르고 버튼 누르는 횟수
if (ans < 0) {
ans = -ans; // 음수면 절대값으로 변경
}
for (int i = 0; i <= 1000000; i++) {
int c = i;
int len = possible(c); // 숫자 개수
if (len > 0) { //0보다 크면 이동가능, 100->c 숫자 눌러 이동함, 버튼 누르는 횟수 len
int press = c - n; // +/- 버튼 누르는 갯수
if (press < 0) {
press = -press;
}
if (ans > len + press) {
ans = len + press; // +/- 버튼 누르는 갯수가 더 적으면 ans 바꾸기
}
}
}
System.out.println(ans);
}
private static int possible(int c) {
//c로 이동 가능하면 c 숫자 갯수 리턴해주는 메소드, 불가능하면 0리턴
if (c == 0) {
if (broken[0]) {
return 0; // 고장났으면 0 리턴
} else {
return 1; // 안 고장이면 1 리턴, 이동할 수 있다
}
}
int len = 0;
while (c > 0) {
if (broken[c % 10]) { // c를 10으로 나눈 나머지 값을 구하고 고장 확인
return 0;
}
len += 1;
c /= 10; // 5457 -> 545 -> 54 -> 5
}
return len;
}
}
-> 브루트포스 의미를 더 잘 이해할 수 있었던 문제. 어차피 모든 채널을 다 돌아도 ans엔 최소값으로만 변동되니까 [+/- 그냥 누르기 vs 숫자버튼 누르고 +/-누르기]를 범위의 채널을 다 돌면서 비교하기… 이런 사고에 익숙하지 않아서 너무 어려웠다 진짜 풀이를 봐도 이해하는데 한참 걸림..ㅠㅠ
이해하기 힘들면 for (int i = 0; i <= 40; i++) 이런식으로 조건 바꾸고 System.out.println("len "+len+" c "+c+" press "+press+" ans "+ans);을 for문 끝에 넣어서 입력27 2 2 5 이런 식으로 넣고 프로그램 흐르는 과정을 좀 보면 됨ㅠㅠㅠㅠㅠㅠ 정답율 22.412% 인걸 위안으로 삼으며.. 나만 어려운게 아닐거야
테트로미노(14500번)
https://www.acmicpc.net/problem/14500
문제
- 폴리오미노는 크기가 1x1인 정사각형을 여러 개 이어 붙여 만든 도형
- 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 총 5가지가 있음
- NxM 크기의 종이 위에 테트로미노를 하나 놓아 놓인 칸에 쓰여 있는 수의 합을 최대로 하는 문제
- 4 ≤ N,M ≤ 500
입력
첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
풀이
- 모든 테트로미노를 넣을 수 있는 경우의 수 구하기
- 회전, 대칭 가능함. 긴건 2개, 정사각형은 1개, ㄴ은 8개, 번개는 4개, ㅜ는 4개 = 더해서 19가지
- ㅡ : N(M-3) 가지, ㅣ : (N-3)xM 가지
- □ : (N-1) x (M-1) 가지
- 즉 모든 방법이 어떤 하나의 칸을 N x M에 놓을 수 있는 방법의 갯수와 같음. 각각의 방법은 O(NM) 전체는 19xO(NM), 즉 시간복잡도 O(NM)
- 모든 경우의 수 500² = 250000 모든 경우의 수 만들어도 ok
- 배경 정사각형은 가장 왼쪽 위를 기준으로 잡음. 회전 모양도 각각 기준을 잡아줌.
- (i,j) : 테트로미노의 기준으로 해서 19가지 다 구현해주기, 단점은 실수를 찾기가 매우 어려움
- 1번 방법과 같은데 (i,j) (i, j+1) (i,j+2) (i+1,j+2) 1번은 이렇게 했다면 (i,j) 기준을 잡아서 i,j가 얼만큼 변하는지 새로운 블록에 넣어주기(19개). 1보다 코드 길이가 짧고 실수 찾기가 더 간단함! 밑에 for문이 잘못되면 아예 안 돌아갈테니 19개 중에서만 잘못된거 있는지 확인하면 되니까.
- 실제 블럭 만들고 블럭을 대칭, 회전시키며 하는 방법인데 이 문제엔 적합치가 않다.
2번 방법 코드
import java.util.*;
public class Main {
static int[][][] block = {
{ {0,1}, {0,2}, {0,3} },
{ {1,0}, {2,0}, {3,0} },
{ {1,0}, {1,1}, {1,2} },
{ {0,1}, {1,0}, {2,0} },
{ {0,1}, {0,2}, {1,2} },
{ {1,0}, {2,0}, {2,-1} },
{ {0,1}, {0,2}, {-1,2} },
{ {1,0}, {2,0}, {2,1} },
{ {0,1}, {0,2}, {1,0} },
{ {0,1}, {1,1}, {2,1} },
{ {0,1}, {1,0}, {1,1} },
{ {0,1}, {-1,1}, {-1,2} },
{ {1,0}, {1,1}, {2,1} },
{ {0,1}, {1,1}, {1,2} },
{ {1,0}, {1,-1}, {2,-1} },
{ {0,1}, {0,2}, {-1,1} },
{ {0,1}, {0,2}, {1,1} },
{ {1,0}, {2,0}, {1,1} },
{ {1,0}, {2,0}, {1,-1} },
};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[n][m];
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
arr[i][j] = sc.nextInt();
}
}
int ans = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) { // 기준(i,j)에 대해서
for(int k=0; k<19; k++) { // 19개 중 k번째 블럭 놓기
boolean ok = true;
int sum = arr[i][j]; // 종이기준 정하고
for(int l=0; l<3; l++) {
int x = i+block[k][l][0];
int y = j+block[k][l][1];
if(0<=x && x<n && 0<=y && y<m) {
sum += arr[x][y]; // 좌표의 x,y번째 값을 더하기
} else {
ok = false;
break;
}
}
if(ok && ans < sum) {
ans = sum;
}
}
}
}
System.out.println(ans);
}
}
-> 1번이 직관적으로 작성+이해하긴 쉬운데 2번 코드는 좀 생각을 많이 해야한다. 익숙해지면 2번처럼 짜는게 더 편한 날이 오겠지?^_ㅠ
댓글남기기