[백준] 10819번 차이를 최대로 JAVA (자바) 풀이

문제 10819번 (브루트포스, 백트래킹)

 

 :  N개의 정수로 이루어진 배열 A

    배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구해라

 

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

 

 

 [입력]

 :  첫째 줄에 N (3 ≤ N ≤ 8)

 :  둘째 줄에는 배열 A에 들어있는 정수 ( -100 ≤ 정수 ≤ 100 )

 

 

 [출력]

 :  식의 최댓값을 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹

 

 수열을 모두 바꿔가며 max 값을 찾기 때문에 브루트포스가 맞다

 

 종료 조건) depth==N

 N개의 숫자를 모두 뽑았기 때문에 종료하고 sum 계산 후 result로 max값 뽑아내기

 

 1. 계산은 if문에서

• 계산은 sum객체에 저장

 

 2. 숫자 뽑아서 배열 변경은 for문에서

• back 메서드 내에서 2번째 for문을 통해 숫자들을 뽑고 배열 변경하는 건 cal[]에 저장
• 시작 지점을 0부터 순차적으로 늘리고 다음 숫자들은 back 재귀를 통해 뽑기 
  순회가 끝나면 visit을 다시 false로 돌리고 시작지점을 변경한다               

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N, arr[], cal[];
    static int result = 0;
    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];
        cal = 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());
        }
        
        
        back(0);
        System.out.println(result);
    }
    
    static void back(int depth){
        if(depth==N){
            int sum = 0;
            for(int i=0;i<N-1;i++){
                sum += Math.abs(cal[i]-cal[i+1]);
            }
            result = Math.max(result, sum);
            return;
        }
        
        for(int i=0; i<N; i++){
            if(!visit[i]){
                visit[i]=true;
                cal[depth]=arr[i];
                back(depth+1);
                visit[i]=false;
            }
        }
    }
    
}

 

 [해설]
     

 :  static int N, arr[], cal[];
    static int result = 0;
    static boolean visit[];

 :  BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());  첫째줄 입력
    arr = new int[N];  숫자 배열
    cal = 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());
     }
        
        
 :  back(0);  백트래킹 시작
        System.out.println(result);  결과 출력
    }
    
 :  static void back(int depth){  depth로 숫자 몇 개 뽑았는지 카운트
        if(depth==N){  N개 다 뽑음 연산 시작
            int sum = 0;
            for(int i=0;i<N-1;i++){ 
                sum += Math.abs(cal[i]-cal[i+1]);  (i번째 수) - (i+1번째 수) 의 절대값 구하기
            }
            result = Math.max(result, sum);  위에서 합산한 sum을 토대로 max값 뽑기
            return;
        }
        
        for(int i=0; i<N; i++){
            if(!visit[i]){  방문 전이라면
                visit[i]=true;  방문처리
                cal[depth]=arr[i];  cal에 변경된 숫자 저장
                back(depth+1);  다음 배열인덱스에 저장할 숫자 택
                visit[i]=false;  끝나면 순서 하나씩 바꾸기위해 다시 false처리
            }
        }
    }
    
}


  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *