[JAVA] 백준 10819번 차이를 최대로 (PERMUTATION_재귀 사용)

차이를 최대로 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

19037

12138

9363

64.253%

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1 복사

6
20 1 15 8 4 10

예제 출력 1 복사

62

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

메모

---

풀이방법 :

N개의 원소중 N 개를 뽑아 줄을 세우는 순열을 만들어 만들어진 순열을 계산해 MAX 값과 비교해 업데이트 해주면됩니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class bj_10819 {
	static int N; // 원소의 갯수
	static int[]map; // 원소배열
	static int max; // max 값
	static boolean visit[]; // 방문했는지 표시
 	static int[] answer; // 순열 배열 
	public static void main(String[] args) throws NumberFormatException, IOException {
		max=0;
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(bf.readLine());
		map = new int[N];
		StringTokenizer st = new StringTokenizer(bf.readLine());
		for(int i=0; i<N;i++) {
			map[i] =Integer.parseInt(st.nextToken());
		} //
		answer= new int[N];
		visit = new boolean[N];
		permutation(0);
		System.out.println(max);
		
		
	}
	
	static void permutation(int cnt) { //NPN 을 하는 순열 코드 
		if(cnt==N) { // N개를 다뽑았을때
			int temp=0;
			for(int i=0; i<N-1;i++) {
				temp= temp+Math.abs(answer[i]-answer[i+1]); // temp 에 값을 계산해 max와 비교후 큰값을 업데이트
			}
			max= Math.max(max, temp);
			return;
		}
		
		for(int i=0; i<N;i++) {
			if(visit[i]) { //이미 뽑은 원소일때
				continue;
			}
			visit[i]=true; // 이원소를 뽑음
			answer[cnt]=map[i]; // 순열 배열에 cnt 위치에 삽입
			permutation(cnt+1); // 다음 재귀로 넘어감
			visit[i]= false; // 안뽑은경우로 바꿔줌 
			
		}
	}
}