10819. 차이를 최대로 (초등학생도 이해 가능) 🐲

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

 

---

풀이

 

<최종 제출 코드>

from itertools import permutations

n= int(input())
nums = list(map(int, input().strip().split()))
each_diff = []

for perm in permutations(nums):
    diff_sum= sum([abs(perm[i] - perm[i+1]) for i in range(len(perm)-1)])
    each_diff.append(diff_sum)
    
result = max(each_diff)
print(result)

 

설명

 

브루트포스 완전탐색으로 모든 합을 구해보고 그 중 최대값을 뽑아보자.

itertools 모듈의 permutations(순열) 함수를 사용했다.

itertools는 반복 가능한 자료형(리스트, 튜플 등)에 대해 유용한 함수들을 제공하여, 더 복잡한 반복 처리와 조합을 쉽게 구현할 수 있게 합니다.

 

1. 입력값을 받아서 하나의 리스트로 (공백을 제거한 후 다시 나눠서) 저장한다.

 

 

2. 순열을 만든다.

 

3. 만들어진 순열을 리스트로 취급하고, 인덱스로 차를 구해보자

차는 바로 앞 인덱스의 원소를 빼는 연산을 할 것이다.

from itertools import permutations
#모든 순열에서 각 원소들간의 차이를 합하고, 이 합한 결과를 B라는 리스트에 정리한다면,
#B의 원소들 중 최대값을 출력하면 된다.

n= int(input())

nums = list(map(int, input().strip().split()))
#nums = [20, 1, 15, 8, 4, 10]

#순열을 만든다.
for perm in permutations(nums):
    #여기서 print(perm) 하면 (20, 1, 15, 8, 4, 10) ~ (10, 4, 8, 15, 1, 20) 쭉 출력
    
    #1번째부터 n번째까지 놓여있는 원소간의 차를 구하고, 하나의 차가 구해질 때마다 결과에 더한다.
    #더한 결과를 하나의 배열이나 리스트에 원소로 저장을 하고 이들 중 최대값을 구한다.
    # i+1까지의 인덱스까지 차를 구해야 하므로 전체 길이에서 1을 빼야 마지막 인덱스까지만 취급
    diff = [abs(perm[i] - perm[i+1]) for i in range(len(perm)-1)]
    print(diff)

 

 

 

4. 원소들로 저장된 이 차(diff)들을 더 해 줍니다. 이 더한 결과를 diff_sum 이라고 해 보지요

 

5. sum은 위에서 더 간단하게 써 줄 수 있습니다.

diff => diff_sum 이라고 리스트명을 변경하고 우항에 sum()을 씌워줍니다.

🤙이 sum은 for문 밖에 each_diff라는 리스트를 선언하고 append()를 통해 추가해 줍니다.

 

6. for문 밖으로 나와 result라는 변수를 하나 만들어서 여기에 each_diff 리스트의 원소 중 최대값을 찾아 할당합니다.

result를 호출합니다.

import os
import sys
os.chdir(os.path.dirname(__file__))
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')

from itertools import permutations
#모든 순열에서 각 원소들간의 차이를 합하고, 이 합한 결과를 B라는 리스트에 정리한다면,
#B의 원소들 중 최대값을 출력하면 된다.

n= int(input())

nums = list(map(int, input().strip().split()))
#nums = [20, 1, 15, 8, 4, 10]

each_diff = [] #! 여기

#순열을 만든다.
for perm in permutations(nums):
    #여기서 print(perm) 하면 (20, 1, 15, 8, 4, 10) ~ (10, 4, 8, 15, 1, 20) 쭉 출력
    
    #1번째부터 n번째까지 놓여있는 원소간의 차를 구하고, 하나의 차가 구해질 때마다 결과에 더한다.
    #더한 결과를 하나의 배열이나 리스트에 원소로 저장을 하고 이들 중 최대값을 구한다.
    # i+1까지의 인덱스까지 차를 구해야 하므로 전체 길이에서 1을 빼야 마지막 인덱스까지만 취급
    diff_sum= sum([abs(perm[i] - perm[i+1]) for i in range(len(perm)-1)]) #*sum 씌움
    #print(diff)하면 [19, 14, 7, 4, 6]부터 [6, 4, 6, 14, 19]까지 나옴
    
    #차들을 합해줍니다. diff = 에 sum( )으로 [abs 이하생략] 형태로 된 리스트를 넣어줍니다.
    ## * diff = 도 => diff_sum 으로 변경해 줍니다.
    #print(diff_sum)하면 50부터 각종 합들이 나옴. 중복되어도 상관은 없다.
    
    #! for문 위에 each_diff 라는 이름으로 리스트를 생성하고 
    # 여기 아래에 append문으로 리스트에 저장해 줍니다.
    each_diff.append(diff_sum)
    #print(each_diff)하면 [50] ~ [50, 48, ,,,,아무튼 모든 diff_sum값] 계단처럼 추가됨
    
#최종적으로 최대값을 구해줍니다.
#최종 최대값은 result 라고 하죠
result = max(each_diff)
print(result)

 

 

 

---

또다른 풀이

# greedy
# 작은거 절반, 큰거 절반으로 나눠서 번갈아 배치하는 게 우월전략이다.
# 맨 끝에 오는 건 한 번만 비교되므로, 차가 가장 적은 조합으로 와야 한다.

n = int(input())
numbers = list(map(int, input().split()))
numbers.sort()
ans = 0
mid = n >> 1

for i in range(mid):
    ans += numbers[n - i - 1] - numbers[i]
ans <<= 1

if n & 1:
    ans -= min(numbers[mid] - numbers[mid - 1], numbers[mid + 1] - numbers[mid])
else:
    ans -= numbers[mid] - numbers[mid - 1]

print(ans)

 

 

설명

 

주석을 읽어보니 처음에 내가 원하던 접근방식을 써 놓은 코드이다.

근데 그리디 아직 안 배워서 그냥 참고용으로 쓰고 간다.

그리디 배우고 다시 보기

 

reference

 

https://sdesigner.tistory.com/51

[백준 알고리즘] 10819번 Python 풀이