문제 : boj10819
N이 최대 8밖에 안된다. 8개의 수로 만들 수 있는 모든 경우를 확인해봐도 O(N!) 이므로 그냥 모든 경우를 확인해보면 된다.
재귀나 스택을 사용한 dfs로 짜면 완전탐색(=brute force)을 쉽게 짤 수 있다. 단순 반복문으로 짜려고 하면 최대 8중첩 반복문이 필요하다 ㅋㅋ
재귀에 익숙치 않다면 방문체크가 어려울 수 있다. 다음 수를 선택하기 전에(내부에서 dfs를 다시 부르면서 cnt+1 해주는 부분이 다음 수를 선택하기 위한 부분이다.) 방문체크를 하고, 반환된 후에 다시 방문체크를 해제해줘야 모든 경우를 볼 수 있다.
코드 : github
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
boolean[] v;
int[] arr;
int answer = 0;
int n;
private void dfs(int cnt, int bf, int sum) {
if (cnt == n) {
answer = Math.max(answer, sum);
return;
}
for (int i = 0; i < n; i++) {
if (v[i]) continue;
v[i] = true;
dfs(cnt+1, arr[i], cnt==0 ? 0:sum+Math.abs(bf-arr[i]));
v[i] = false;
}
}
private void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
arr = new int[n];
v = new boolean[n];
for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
dfs(0, 0, 0);
System.out.println(answer);
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}
'PS > BOJ' 카테고리의 다른 글
백준 10465 자바 - Rolling Encryption (BOJ 10465 JAVA) (0) | 2022.01.02 |
---|---|
백준 6588 자바 - 골드바흐의 추측 (BOJ 6588 JAVA) (0) | 2022.01.01 |
백준 2491 자바 - 수열 (BOJ 2491 JAVA) (0) | 2021.12.31 |
백준 2225 자바 - 합분해 (BOJ 2225 JAVA) (0) | 2021.12.30 |
백준 2133 자바 - 타일 채우기 (BOJ 2133 JAVA) (0) | 2021.12.30 |
댓글