[백준] code.plus(브루트포스-순열,JAVA)10819번, 차이를 최대로

문제 링크

10819번: 차이를 최대로

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

순열이란

n개의 원소를 중복없이 나열하는 것입니다.

순열 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 배열은 N개의 입력된 수로 이루어진다.

2. 배열의 수는 중복이 불가능하다. = 순열이다.

3. 차이의 절대값의 합에 최대값을 출력해야 한다.

 

배열

permutation  : 현재 경우의 순열

 

check : 배열에 값이 순열에 사용되었는지 확인하는 배열

 

num : 배열에 들어갈 수 있는 N개의 수 저장

 

permutation, check, num와 재귀를 이용하여 모든 경우의 순열을 구하였습니다.

 

문제를 해결할 때에 만들 수 있는 모든 경우의 순열을 만들었습니다.

순열에 들어갈 값을 저장할 때마다 차이의 절대값의 합도 같이 구하였습니다.

 

문제에 해결알고리즘은

1. N개의 수 중 첫 번째 순열에 값을 지정하고 해당 check를 true로 바꾸어주었습니다.

2. 순열의 모든 경우의 수를 구하였습니다.

3. 순열의 들어갈 수를 저장할 때마다 차이의 절대값을 더해주었습니다.

4. 순열이 완성되었을 때 차이의 절대값의 합을 이전 순열의 값과 비교하여 가장 큰 값을 찾았습니다.

5. 모든 순열을 탐색한 뒤 가장 큰 값을 결과로 출력하였습니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• 모든 경우의 순열에서 차이 절대값의 최대합을 구하는 maxDif 함수를 만들었습니다.
• BufferedWriter에 차이 절대값의 최대합을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• maxDif는 num, permutation, check와 재귀를 사용하여 모든 순열에 차이 절대값 합을 구하였습니다.
• maxDif는 순열이 완성되었을 때 최대값과 비교하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N;	//입력되는 숫자의 개수
	public static int[] num,permutation;	//N개의 입력된 숫자, 순열 값 저장
	public static boolean[] check;		//N개의 숫자 사용되었는지 확인 배열
	public static int max = Integer.MIN_VALUE;		//차이 절대값의 최대합
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 배열 초기화---------
    	N = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	num = new int[N];
    	permutation = new int[N];
    	check = new boolean[N];
    	for(int i=0;i<N;i++) {
    		num[i] = Integer.parseInt(st.nextToken());
    	}
        //순열 첫 번째 값 저장 후 함수 실행
        /*
        이유는 처음이 [1]-[0]을 진행해야 하는데
        함수에 순열에 처음 들어가는 수의 인덱스가 [0]이면
        [0] - [-1]로 ArrayIndexBound 에러가 발생하기 때문에
        첫 번째 순열 값은 저장하고 함수를 실행하였습니다.
        */
    	for(int i=0;i<N;i++) {
    		check[i] = true;
    		permutation[0] = num[i];
    		maxDif(1, 0);
    		check[i] = false;
    	}
    	bw.write(max + "\n");		//차이 절대값의 최대합 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //-----순열의 차이 절대값의 최대합 구하는 함수---------
    public static void maxDif(int length, int cur) {
    	if(length==N) {		//순열 완성시
    		max = Math.max(max, cur);		//최대값 비교
    		return;
    	}
        //-------순열의 들어갈 숫자 탐색-------
    	for(int i=0;i<N;i++) {
    		if(!check[i]) {
    			check[i] = true;
    			permutation[length] = num[i];
                	//차이 절대값 합 구하는 과정
    			int temp = Math.abs(permutation[length-1] - permutation[length]);
    			maxDif(length+1, cur+temp);		//재귀 발생
    			check[i] = false;
    		}
    	}
    	return;
    }
}