[백준10819] 차이를 최대로

문제

---

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

10819번: 차이를 최대로

 

생각의 흐름

---

1. 이전에 포스팅했던 모든순열의 로직을 이용해 가능한 모든 순열에 대해 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|의 값을 구한다.
2. 주의할 점은 중복된 원소(즉, 같은 수)가 있을 수 있으므로 비교 시에 등호를 넣어주어야 한다.
3. 위 식의 최댓값을 찾는다.

 

코드

---

def next_permutation(arr):

    n = len(arr)-1
    i = n
    # 중복된 원소 있을 수 있으므로 부등호에 =를 포함시켜 주어야 함
    while arr[i-1] >= arr[i]:
        i -= 1

    j = i-1
    diff = 10000
    position_to_switch = 0

    # select the number to chage position
    for k in range(i, n+1):
        if arr[k]-arr[j] > 0:
            diff = min(diff, arr[k]-arr[j])
    for m in range(i, n+1):
        if arr[m]==arr[j]+diff:
            position_to_switch = m
            break

    # change position of two number
    temp = arr[j]
    arr[j] = arr[position_to_switch]
    arr[position_to_switch] = temp

    temp_list = arr[j+1:]
    temp_list.sort()
    arr = arr[:j+1]
    arr = arr + temp_list

    return arr

if __name__=='__main__':

    num = int(input())
    arr = []
    arr = list(map(int, input().split()))
    arr.sort()

    # the number of permutation
    per_num = 1
    for i in range(num):
        per_num *= (i+1)
    per_num
    per_num = per_num - 1

    # calculate for the first list
    sum_list = []
    temp_sum = 0
    for i in range(num-1):
        temp_sum += abs(arr[i] - arr[i+1])
    sum_list.append(temp_sum)
    

    for _ in range(per_num):
        temp_sum = 0
        arr = next_permutation(arr)
        
        for i in range(num-1):
            temp_sum += abs(arr[i] - arr[i+1])
        sum_list.append(temp_sum)

    print(max(sum_list))