[백준 문제] P10819 차이를 최대로(파이썬)
[백준 문제] P10819 차이를 최대로(파이썬)
내 답안
# 1. 다음 순열을 만드는 함수
def next_permutation(a):
n = len(a) - 1
i = n
while i > 0 and a[i-1] >= a[i]:
i -= 1
if i == 0: # 마지막 순열
return False
j = n
while a[i-1] >= a[j]: # 오른쪽에 있으면서 a[i-1]보다 큰 수
j -= 1
a[i-1], a[j] = a[j], a[i-1] # SWAP
j = n
while i < j:
a[i], a[j] = a[j], a[i] # a[i]부터 순열 뒤집기
i += 1
j -= 1
return True
# 2. 공식 계산
def calculate(a) :
ans = 0
for i in range(len(a)-1) :
plus = abs(a[i]-a[i+1])
ans = ans + plus
return ans
# 3. 순열 하나씩 계산
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
ans = 0
while True :
if next_permutation(a) is False :
break
temp = calculate(a);
ans = max(ans, temp);
print(ans)
6
20 1 15 8 4 10
62
하나씩 테스트 하기
def next_permutation(a):
n = len(a) - 1
i = n
while i > 0 and a[i-1] >= a[i]:
i -= 1
if i == 0: # 마지막 순열
return False
j = n
while a[i-1] >= a[j]: # 오른쪽에 있으면서 a[i-1]보다 큰 수
j -= 1
a[i-1], a[j] = a[j], a[i-1] # SWAP
j = n
while i < j:
a[i], a[j] = a[j], a[i] # a[i]부터 순열 뒤집기
i += 1
j -= 1
return True
def calculate(a) :
ans = 0
for i in range(len(a)-1) :
plus = abs(a[i]-a[i+1])
ans = ans + plus
return ans
a = [20, 1, 15, 8, 4, 10] # 19 14 7 4 6 = 33 17 = 50
calculate(a)
50
a = sorted(a)
a
[1, 4, 8, 10, 15, 20]
ans = 0
while True :
if next_permutation(a) is False :
break
temp = calculate(a);
ans = max(ans, temp);
print(ans)
62
