공부 167일차: 백준 10819번 차이를 최대로 자바 java

10819 차이를 최대로

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

 

 

---

백준 10819번 문제 차이를 최대로

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/295

공부 156일차: 백준 15654번 N과 M (5) 자바 java

주어진 숫자들로 이루어진 모든 순열을 구했던 이 문제를 참고하면 도움이 될 것이다

 

 

문제에서 적절한 순서로 바꾸라고 했지만, n의 범위가 매우 좁은 것으로 보아

모든 순열의 경우를 구한 뒤 각자 더해서 비교해보면 될 듯하다

 

어렵지 않은 과정이라 코드를 보면 바로 이해가 될 것이다

 

 

 

---

정답 인정 코드

---

 

1) 모든 순열 저장한 뒤 최댓값 구하기

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, count;
    static int[] arr, nums;
    static boolean[] visited;
    static int[][] permutation;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        nums = new int[n];
        visited = new boolean[n];
        permutation = new int[getSize()][n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        
        DFS(0);
        
        bw.write(getMax()+"");
        bw.flush();
        bw.close();
    }
    
    public static int getSize() {
        int[] dp = new int[10_001];
        dp[2] = 2;
        for(int i = 3; i < n+1; i++) {
            dp[i] = dp[i-1]*i;
        }
        return dp[n];
    }
    
    // DFS 활용하여 전체 순열 구하기
    public static void DFS(int depth) {
        // 입력된 숫자의 깊이까지의 배열 출력
        if(depth == n) {
            if(count < getSize()) {                
                for(int i = 0; i < n; i++) {
                    permutation[count][i] = arr[i];
                }
            }
            count++;
            return;        // 멈추기
        }
        
        for(int i = 0; i < n; i++) {
            // 방문하지 않은 노드라면
            if(!visited[i]) {
                visited[i] = true;    // 방문상태로 변경 후     
                arr[depth] = nums[i];     // 그 깊이의 노드에 값 넣기
                DFS(depth+1);    // 다음 노드 : 깊이+1
                visited[i] = false;    // 다시 false로 돌려서 검사할 수 있도록
            }
        }
    }
    
    static int getMax() {
        // 가장 낮은 수로 시작(문제에서 -100까지 입력 가능하다고 했으므로)
        int max = Integer.MIN_VALUE;    
        for(int i = 0; i < count; i++) {
            int sum = 0;
            for(int j = 0; j < n-1; j++) {
                // |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
                sum += Math.abs(permutation[i][j]-permutation[i][j+1]); 
            }
            max = Math.max(max, sum);
        }
        return max;
    }
}

 

 

2) 순열의 모든 경우의 수를 저장하지 않고 바로바로 최댓값 비교하기

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, count;
    static int max = Integer.MIN_VALUE;
    static int[] arr, nums;
    static boolean[] visited;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        nums = new int[n];
        visited = new boolean[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        
        DFS(0);
        
        bw.write(max+"");
        bw.flush();
        bw.close();
    }
 
    // DFS 활용하여 전체 순열 구하기
    public static void DFS(int depth) {
        // 입력된 숫자의 깊이까지의 배열 출력
        if(depth == n) {
            max = Math.max(getSum(), max);
            return;        // 멈추기
        }
        
        for(int i = 0; i < n; i++) {
            // 방문하지 않은 노드라면
            if(!visited[i]) {
                visited[i] = true;    // 방문상태로 변경 후     
                arr[depth] = nums[i];     // 그 깊이의 노드에 값 넣기
                DFS(depth+1);    // 다음 노드 : 깊이+1
                visited[i] = false;    // 다시 false로 돌려서 검사할 수 있도록
            }
        }
    }
    
    static int getSum() {
        int sum = 0;
        for(int i = 0; i < n-1; i++) {
            sum += Math.abs(arr[i]-arr[i+1]);
        }
        return sum;
    }
}

이 블로그를 참고했다

 

 

 

---

두 번째 경우가 메모리 측면도 시간 측면도 압승

static 변수와 메서드를 어떻게 더 활용할 수 있는지 생각해보아야겠다