10819번 - 차이를 최대로
문제 풀이 시간 : 30분
문제 요약
- N개의 정수가 주어진다.
- 정수의 순서를 바꿔서 아래 식의 최댓값을 구하라
- |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
문제 풀이
이 문제는 오랜만에 자바로 알고리즘 과제를 하려고 하니 머리가 하얘져서 자바로 백준을 좀 풀어봐야겠다는 생각으로 선정했다.
이 문제는 경우의 수가 그렇게 많지 않기 때문에 모든 경우의 수를 확인하면서 최댓값을 구하는 방식으로 코드를 짰다.
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int result=0,n;
public static boolean[] visited;
public static int[] temp;
public static int[] input;
public static void find(int cnt){
if(cnt==n){ //모든 수 탐색했으면 식 계산
int sum = 0;
for(int i=0;i<n-1;i++){
sum+=Math.abs(temp[i]-temp[i+1]);
}
result=Math.max(result,sum); //result 업데이트
return;
}
for(int i=0;i<n;i++){
if(!visited[i]){
temp[cnt]=input[i];
visited[i]=true;
find(cnt+1);
visited[i]=false;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
input = new int[n];
temp = new int[n];
visited = new boolean[n];
for (int i = 0; i < n; i++)
input[i] = Integer.parseInt(st.nextToken());
find(0);
System.out.println(result);
}
}
근데 몇개 글을 읽어보다가 다른 방법도 있다는 것을 알게되었다.
주어진 정수를 정렬해서 순서대로 배열에 넣으면 되는거다.
1) max1 min1
2) min2 max1 min1 max2
3) max3 min2 max1 min1 max2 min3
이런식으로 번갈아가며 앞뒤로 붙여준다.
예를들어 주어진 배열이 1 2 3 4 5 6 이라면
1) 6 1
2) 2 6 1 5
3) 4 2 6 1 5 3
위와 같이 배열을 만들어주면 위의 식을 계산했을 때 최대값이 나온다.
다른 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
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());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] input = new int[n];
for (int i = 0; i < n; i++)
input[i] = Integer.parseInt(st.nextToken());
Arrays.sort(input);
ArrayList<Integer> arr = new ArrayList<>(n);
int i;
for (i = 0; i < n / 2; i++) { //번갈아가며 배열에 수 추가
if (i % 2 == 0) {
arr.add(0, input[n - 1 - i]);
arr.add(input[i]);
} else {
arr.add(0, input[i]);
arr.add(input[n - 1 - i]);
}
}
if(n%2!=0){ //만약 수가 홀수개면 제일 앞,뒤에 넣었을 경우 비교해서 추가
if(Math.abs(arr.get(0)-input[i])>Math.abs(arr.get(arr.size()-1)-input[i])){
arr.add(0,input[i]);
}
else{
arr.add(input[i]);
}
}
int ans=0;
for(i=0;i<n-1;i++)
ans+=Math.abs(arr.get(i)-arr.get(i+1));
System.out.println(ans);
}
}
함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.