[백준/JAVA] 10819번: 차이를 최대로

🔺 문제 

10819번: 차이를 최대로

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, result;
    static int[] A, tmp;
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        tmp = new int[N];   // 📍 각 순열 케이스를 담을 임시 저장 배열
        visited = new boolean[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        dfs(0);
        System.out.println(result);
    }
    
    // 🔔 백트래킹 🔔
    private static void dfs(int cnt) {
        if(cnt == N) {
            int sum = 0;
            for(int i = 0 ; i < N - 1 ; i++) {
                sum += Math.abs(tmp[i] - tmp[i + 1]);
            }
            result = Math.max(result, sum);
            return;
        }
        
        for(int i = 0 ; i < N ; i++) {
            if(visited[i])  continue;
            
            visited[i] = true;
            
            tmp[cnt] = A[i];    // 📍 담음
            dfs(cnt + 1);       // 🔔 재귀로 만들고, 그 다음 idx 늘리기
            
            visited[i] = false; // ⭐ 다 만들고 false로 방문 해제
        }
    }
}

✅ 해결 아이디어
✔ 브루트포스 & 백트래킹
1) N의 값이 크지 않으므로, 배열로 만들 수 있는 모든 수열들의 케이스 조사 (순열 개념)
2) 각 배열로 구한 값들 중 가장 큰 값 출력

→ 브루트포스로 중복되지 않게 모든 경우의 수 확인 가능

 

 

💥 유의사항

• 경우의 수 저장하는 자료구조 필요! (여기서는 int[] 사용)

 

---

🔺 다른 풀이들

- 다들 비슷하심..

---

💬 느낀 점

재귀... 브루트포스.. 백트래킹을 잘하자...

아자잣..

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이, 해설 참고

[백준] 10819번 자바 차이를 최대로

[백준] 10819 : 차이를 최대로 (JAVA)

 

[BOJ - JAVA] 10819 - 차이를 최대로(완전탐색, 백트래킹)