반응형
10819번: 차이를 최대로
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
www.acmicpc.net
착오 )
처음에는 그리디하게 접근하려고 했다.
입력받은 배열을 정렬한 이후 배열의 앞부터 가장 큰 수와 가장 작은 수를 번갈아가면서 저장하려고했지만 이런 방법으로는 안된다는 것을 반례를 통해 알게되어 다른 방법으로 접근했다.
이 방법을 좀더 개선한다면 그리디로 풀 수 있을 거라고 생각된다.
풀이 )
입력받은 배열의 모든 순열에 대해서 결과값을 비교하면서 최댓값을 구했다.
다음 순열에 대해서는 nextPermutation( ) 메서드를 구현해서 사용했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < n; ++i)
arr[i] = Integer.parseInt(st.nextToken());
Arrays.sort(arr);
int ans = -(int)1e7;
do{
ans = Math.max(ans, cal(arr));
} while(nextPermutation(arr));
System.out.println(ans);
}
static boolean nextPermutation(int[] arr) {
int len = arr.length;
int i=len-1;
while( i>0 && arr[i-1] >= arr[i] )
--i;
if(i==0)
return false;
int j = len-1;
while(arr[i-1]>=arr[j])
--j;
int tmp = arr[i-1];
arr[i-1] = arr[j];
arr[j] = tmp;
int k = len-1;
while(i<k) {
tmp=arr[i];
arr[i++]=arr[k];
arr[k--]=tmp;
}
return true;
}
static int cal(int[] arr){
int len = arr.length;
int ret = 0;
for(int i = 1; i < len; ++i)
ret += Math.abs(arr[i]-arr[i-1]);
return ret;
}
}반응형
'문제풀이 > 백준' 카테고리의 다른 글
| [JAVA] 백준 - 17612 : 쇼핑몰 (0) | 2021.04.02 |
|---|---|
| [JAVA] 백준 - 2263 : 트리의 순회 (0) | 2021.02.28 |
| [JAVA] 백준 - 17142 : 연구소 3 (0) | 2021.02.26 |
| [JAVA] 백준 - 16235 : 나무 재테크 (0) | 2021.02.23 |
| [JAVA] 백준 - 1946 : 신입 사원 (0) | 2021.02.17 |
