[BAEKJOON]10819 차이를 최대로

문제 요약

• 알고리즘 분류: 백트래킹, 순열
• 난이도: Silver2
• 문제내용:
  • 정수의 순서를 바꿔서 아래 같은 식의 최댓값을 구하여라
  • |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

• 사이트 주소: https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.

https://jih3508.tistory.com/84

[알고리즘 이론] 백트래킹(Backtracking)

접근 방법 

  이번 문제에서는 백트레킹에서 순열을 구현만 하면 되는 문제이다. 구현하는 방법은 아래 같이 하면된다.

1. 큰 숫자를 저장할 숫자를 0으로 초기화 한다.
2. 재귀 호출할 함수를 만든다.
   • 재귀 호출 파라미터를 K라고 할때 K는 0으로 시작한다.
   • K부터 시작해 N - 1까지 반복문을 돌린다.
   • 반복문 i번째와 K번째 배열 위치 바꾼다.
   • 파라미터 K + 1로  재귀 함수 호출한다.
   • 재귀 호출 끝나고 반복문 i번째와 K번째 배열 위치 다시 바꾼다.
   • 0부터 시작해서 K가 길이 N이 같을때 위 계산을 하고 이전 최대 값이랑 비교해서 최대값을 구한다.

 순열 백트레킹 구현은 코드 아래와 같이 구현이 가능하기 때문에 외워두면 도움이 많이 될것이다.

Python

def permutations(k = 0):
    global max_num
    if(k == N):
        # To-Do
        return
    else:
        for i in range(k, N):
            array[k], array[i] = array[i], array[k]
            permutations(k + 1)
            array[k], array[i] = array[i], array[k]

Java

public static void permutations(int k) {
		
		int tmp;
		
		if (k == N) {
			//To-Do
			return;
		}else {
			for(int i = k; i < N; i++) {
				tmp = array[i];
				array[i] = array[k];
				array[k] = tmp;
				permutations(k + 1);
				array[k] = array[i];
				array[i] = tmp;

			}
		}
	}

 

Code

Python

 파이썬으로 백트레킹으로 구현이 가능하지만 permutations 외부 모듈에서 제공해주기때문에 2가지 방법으로 구현을 하는것을 보여 주겠다.

백트레킹

def permutations(k = 0):
    global max_num
    if(k == N):
        max_num = max(sum([abs(array[i] - array[i + 1]) for i in range(N - 1)]), max_num)
        return
    else:
        for i in range(k, N):
            array[k], array[i] = array[i], array[k]
            permutations(k + 1)
            array[k], array[i] = array[i], array[k]

N = int(input())
array = list(map(int, input().split()))
max_num = 0

permutations()

print(max_num)

permutations 

from itertools import permutations

N = int(input())
array = list(map(int, input().split()))
max_num = 0

for arr in permutations(array):
    max_num = max(max_num, sum([abs(arr[i] - arr[i + 1]) for i in range(N - 1)]))

print(max_num)

 

Java

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

public class Main {
	
	static int[] array;
	static int max_Num = 0;
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		array = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		permutations(0);
		System.out.println(max_Num);
	}
	
	public static void permutations(int k) {
		
		int tmp;
		
		if (k == N) {
			int value = 0;
			for(int i = 0; i < N - 1; i++) {
				value += Math.abs(array[i + 1] - array[i]);
			}
			max_Num = Math.max(max_Num, value);
			return;
		}else {
			for(int i = k; i < N; i++) {
				tmp = array[i];
				array[i] = array[k];
				array[k] = tmp;
				permutations(k + 1);
				array[k] = array[i];
				array[i] = tmp;

			}
		}
	}
	
}