목록브루트포스 (14)
Dev.baelanche
[백준 7453] 합이 0인 네 정수
A, B, C, D 배열의 각각을 더해서 0과 비교하기에는 시간이 너무 오래걸린다. 1. A, B의 모든 부분합을 저장한 배열을 만든다. (C, D의 부분합 배열이어도 상관없다.) 2. C, D의 모든 부분합을 저장한 Map을 만든다. 부분합 중 중복된 수가 있다면 카운트를 올린다. Map의 Key를 sum, Value를 카운트로 사용했다. 3. A, B의 부분합 배열과 Map의 원소들을 비교하며 두 원소의 합이 0일 경우 카운트만큼 개수를 올린다. 코드는 알아보기 꽤나 쉽다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int temp..
[백준 10974] 모든 순열
신나는 완전탐색 문제다. 방문배열을 백트래킹 하며 진행했다. public class Main { static int n; static boolean visited[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); visited = new boolean[n+1]; dfs(0, ""); } public static void dfs(int cnt, String s) { if(cnt == n) { System.out.println(s); return; } for(int i=1; i
[백준 2589] 보물섬
육지중에 가장 멀면서 빠른 길을 찾으라는 문제이다. 문맥이 참;; 배열 크기가 50*50이니 육지인 인덱스마다 BFS를 해주며 완전탐색하면 된다. public class Main { static int n; static int m; static int a[][]; static boolean visited[][]; static int dx[] = {-1, 0, 0, 1}; static int dy[] = {0, -1, 1, 0}; static int max = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri..
[백준 14500] 테트로미노
N*M 배열에서 테트로미노를 놓을 수 있는 경우를 모두 체크한다. 코드를 보면 구현방식을 아주 쉽게 알 수 있다. public class Main { static int a[][]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); a = new int[n][m]; ..
[백준 6603] 로또
중복되지 않으면서 오름차순인 수열을 완전탐색한다. 빈 줄을 끼워넣는 것을 유의한다. public class Main { static int a[]; static int k; static boolean f = true; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; while(true) { st = new StringTokenizer(br.readLine()); k = Integer.parseInt(st.nextToken()); if(k == 0) break; a = new int[k..
[백준 15683] 감시
감시카메라가 감시 가능한 모든 지역을 탐색하게 한다. 1번은 4가지 경우, 2번은 2가지, 3번은 4가지, 4번도 4가지, 5번은 1가지 경우가 있다. 모든 경우를 완전탐색하기만 하면 되는 문제인데 구현이 좀 까다롭다. public class Main { static int n; static int m; static ArrayList cctv = new ArrayList(); static int ans = Integer.MAX_VALUE; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st..
[백준 1182] 부분수열의 합
배열의 최대길이가 20이므로 전 구간을 완전탐색한다. 처음에 좀 헤맸는데 재귀를 쓰라는 힌트를 보고 풀었다. 메모이제이션 기법만 안썼지 구현방법은 dp 와 다를게 없다. public class Main { static int n; static int s; static int a[]; static int cnt = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); s = sc.nextInt(); a = new int[n]; for(int i=0; i= n) return; sum += a[idx]; if(sum == s) cnt++; recursive(idx + 1, sum - a[..
