[백준] 10819번 차이를 최대로 - Java, 자바
난이도
실버 2
문제
https://www.acmicpc.net/problem/10819
풀이
백트래킹 문제
- 갯수가 n인 조합을 구한다.
백트래킹을 사용하여 depth가 n이 되도록 재귀를 수행하고, 조합의 결과는 result 배열에 저장한다. - depth가 n일 때 = 갯수가 n인 조합의 경우가 나왔을 때, 차이를 최대로 만드는 공식을 사용해 합을 구한다.
- 합이 최대가 되도록 Math.max함수를 사용해 최댓값을 저장한다.
코드
package 백트래킹;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ10819 {
static int n;
static int[] arr;
static int[] result;
static int max = Integer.MIN_VALUE;
static boolean[] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
visit = new boolean[n];
result = new int[n];
back(0);
System.out.println(max);
}
static void back(int depth) {
if (depth == n) {
int sum = 0;
for (int i = 0; i < n - 1; i++) {
sum += Math.abs(result[i] - result[i + 1]);
}
max = Math.max(sum, max);
return;
}
for (int i = 0; i < n; i++) {
if (!visit[i]) {
visit[i] = true;
result[depth] = arr[i];
back(depth + 1);
visit[i] = false;
}
}
}
}
Author And Source
이 문제에 관하여([백준] 10819번 차이를 최대로 - Java, 자바), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmjieun/백준-10819번-차이를-최대로-Java-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)