[백준 10819번] 완전 탐색 기법

 

 

[백준 10819번 - 차이를 최대로]

 

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

10819번: 차이를 최대로

 

(첫번째 시도 - 오답)

생각했던 방법: |가장 큰 수 - 가장 작은 수| + |두번째 큰 수 - 두번째 작은 수| + ... 로 하면 될 것 같았다.

n=int(input())
nums=list(map(int, input().split()))

max=sorted(nums, reverse=True)
min=sorted(nums)

sum=0
for i in range(n//2):
	sum+=max[i]-min[i]

print(sum)

 

(두번째 시도 - 정답)

*메모리 35172KB, 시간 168ms

생각했던 방법: 모든 순열 조합에서 합을 구하고 그 중에서 가장 큰 값을 선택한다.

from itertools import permutations
n=int(input())
arr=list(map(int, input().split()))
ans=[]

for nums in list(permutations(arr)):
    sum=0
    for i in range(0,n-1):
        sum+=abs(nums[i]-nums[i+1])
    ans.append(sum)
    
print(max(ans))

 

 

<공부>

 

◾ sys.stdin.readline()

: 이 문제에서는 sys를 사용해도 시간이 단축되지 않았다. (필자의 경우 오히려 시간이 더 초과되었음)

 ➡ sys는 테스트 예제를 여러 줄 받는 경우 사용한다. (위의 문제는 1줄만 받으므로 별다른 차이가 없음)

import sys
from itertools import permutations
n=int(sys.stdin.readline())
arr=list(map(int, sys.stdin.readline().split()))