[백준/Python]10819: 차이를 최대로

문제

https://www.acmicpc.net/problem/10819
백준 문제집 - 대학생 기본반
알고리즘 분류: 브루트포스, 백트래킹

---

풀이

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

 

 

처음엔 문제를 |A[0] - A[1]| + |A[2] - A[3]| + ... + |A[N-2] - A[N-1]| 로 봤었다.
그래서 한 시도 👉 A 정렬 후 (1번째로 큰 값 - 1번째로 작은 값, 2번째로 큰 값 - 2번째로 작은 값...) 반복하기.

물론 문제 자체를 잘못 봤기때문에 제대로 된 답이 나오지 않았고^^;;

간단하게 permutations로 순열을 생성한뒤 일일이 대입하는 방식으로 풀었다.

 

전체 코드

# 메모리: 31120KB / 시간: 124ms
from sys import stdin
from itertools import permutations


input = stdin.readline

N = int(input())
A = list(map(int, input().split()))

ret = 0

for perm in permutations(A):
    tmp = 0
    for i in range(N-1):
        tmp += abs(perm[i] - perm[i+1])
    ret = max(ret, tmp)

print(ret)

124ms... 나쁘지 않지만 메모리가 31120KB다.
이런 경우 실행시간이 월등히 빠른 풀이가 있을 확률이 99.9998%다.

아니나 다를까 36ms인 풀이가 존재했다.
링크는 👉 https://www.acmicpc.net/source/82156215

 

방식은 내가 처음에 시도했던 방법과 유사하다.
주어진 리스트 A를 정렬한 후, 길이의 절반값인 mid만큼 큰 값 - 작은 값을 반복한다.

그리고 절반만 구해준것이므로 나머지 절반을 더해준다. (2배로 곱하기)

마지막으로 양 끝자리에 올 녀석들을 판단하는건데,
홀수일때와 짝수일때의 경우가 다르다.

 

일단 양 끝에 위치한 원소들은 한번씩만 계산되는 구조다.
하지만 우린 두번씩 계산되는걸 가정해 두배로 곱해준 상태이므로, 양 끝 원소들의 차이값을 한번 빼줘야한다.

 

짝수일 경우, 가운데에 위치한 두 원소 == 양 끝에 위치할 원소이기 때문에 무조건 가운데 두 원소의 차이값을 빼주면 된다.
하지만 홀수일 경우, 가운데 전 원소 - 가운데 원소, 가운데 원소 - 가운데 다음 원소중 어떤 경우가 최선인지 모른다.
따라서 두 경우 중 차이값이 더 작은 경우의 원소를 양 끝에 배치한다.

 

전체 코드

# 참고: https://www.acmicpc.net/source/82156215
from sys import stdin


input = stdin.readline

N = int(input())
A = list(map(int, input().split()))

A.sort()
mid = N // 2

ret = 0
for i in range(mid):
    ret += A[N-i-1] - A[i]

ret *= 2

if N % 2 == 0:
    ret -= A[mid] - A[mid-1]
else:
    ret -= min(A[mid] - A[mid-1], A[mid+1] - A[mid])

print(ret)

 

또는 아래의 풀이를 참고할수도 있다.

# 출처: https://www.acmicpc.net/source/71412622
n = int(input())
a = sorted(list(map(int, input().split())))
min_val = a[0]
max_val = a[-1]
total = max_val - min_val
a = a[1:-1]

while len(a) > 0:
    if len(a) != 1:
        x = a[0]
        y = a[-1]
        total += max_val - x
        total += y - min_val
        max_val = y
        min_val = x
        a = a[1:-1]
    else:
        x = a[0]
        total += max(max_val - x, x - min_val)
        break

print(total)

첫번째 코드보다 좀 더 직관적이다.
길이가 짝수일 경우 if안의 코드만, 홀수일경우 else문까지 실행한다.