[Silver II] 차이를 최대로 - 10819
성능 요약
메모리: 12484 KB, 시간: 104 ms
분류
백트래킹, 브루트포스 알고리즘
제출 일자
2023년 12월 1일 09:40:35
문제 설명
N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.
|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
입력
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
출력
첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.
풀이 방식
1. 완전 탐색으로 숫자배열에서 하나씩 뽑아서 넣어줌(만들 수 있는 경우의 수를 만들어주는 함수)
2. count 가 n이 된다면 계산해줌
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int result, n;
static int[] arr, select;
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];
select = new int[n];
visit = new boolean[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
brute(0);
System.out.println(result);
}
private static void brute(int count) {
// count가 n이라는 건 선택한 배열의 길이가 N이라는 뜻
if (count == n) {
cal();
return;
}
// 0부터 n까지 전부 집어 넣어줌 (대신 방문한 곳은 제외하고)
for (int i = 0; i < n; i++) {
// 방문하지 않은 곳에 로직
if (!visit[i]) {
// 방문
visit[i] = true;
// 값 삽입
select[count] = arr[i];
// 메서드 호출(dfs)
brute(count + 1);
// 방문 해제
visit[i] = false;
}
}
}
// 계산해주는 메서드
private static void cal() {
int sum = 0;
for (int i = 0; i < n - 1; i++) {
sum += Math.abs(select[i] - select[i + 1]);
}
result = Math.max(result, sum);
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 4963번 : 섬의 개수 Silver2(실버 2) - JAVA[자바] (0) | 2023.12.10 |
---|---|
[백준] 10451번 : 순열 사이클 Silver 3(실버 3) - JAVA[자바] (1) | 2023.12.10 |
[백준] 11724번 : 연결 요소의 개수 Silver2(실버2) - JAVA[자바] (0) | 2023.11.30 |
[백준] 11576번 : Base Conversion Silver5(실버5) - JAVA[자바] (0) | 2023.11.29 |
[백준] 1992번 : 쿼드트리 Silver1(실버1) - JAVA[자바] (1) | 2023.11.28 |