[백준 | 실버2] 10819번: 차이를 최대로(순열, itertools permutations)

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

10819번: 차이를 최대로

문제

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

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1 복사

6
20 1 15 8 4 10

예제 출력 1 복사

62

 

문제풀이

정수의 순서를 적절히 바꾸기  -> n개의 리스트에 있는 n개의 개수만큼 그냉 숫자 순서만 바꿔라
최댓값을 구하는 프로그램을 작성

n개의 숫자 리스트중에서 그낭 n개 만큼 순열을 만들어라
(단순 숫자 리스트에서 순서만 바꾸는 순열을 만들라는 뜻)
만들어진 순열 리스트에서 순서대로 두개씩 뽑아서 빼라 
그 차를 합한 값이 최대인 값을 찾아라

 

 

문제해결

 

백트랙킹 이용해서 풀기
다시 뽑기 없는 순열 만드는 방법
for n까지 -> check False 확인 => check True 체크 => DFS(depth+1) => check Fasle 복귀

 

1. 백트랙킹 순열 만든 후 만들기

2. 순열을 이용해서 순서대로 2개 빼줌([i+1] - [i])

3. 뺀 값을 누적 합 시키기

4. 누적 합 값중에서 최대값 찾으면서 최대값 갱신

n = int(input())
num_list = list(map(int, input().split()))
permu_list = []

visited = [False] * n
max_vlaue = -1

def DFS(depth) :
    global max_vlaue

    if depth == n :
        sum_num = 0
        for i in range(n-1) :
            num = abs(permu_list[i+1]-permu_list[i])    #순열로 만든 리스트에서 [i+1]-[i] 두개씩 빼줌
            sum_num += num
        if sum_num > max_vlaue :            #최대 값 찾기
            max_vlaue = sum_num
        return
    else :
        for i in range(n) :
            if visited[i] is False :
                visited[i] = True
                permu_list.append(num_list[i])
                DFS(depth+1)
                visited[i] = False
                permu_list.pop()

DFS(0)

---

itertools의 permutations 사용해서 풀이

itertools.permutations(iterable, r=None) 함수는 iterable 요소의 길이 r에 해당하는 순열을 리턴하는 함수이다.

 

r개 숫자를 따로 표기해 주면 r개 만큼 뽑은 순열 생성

>>> from itertools import permutations
>>> num = list(permutations(['1', '2', '3'], 2))
>>> print(num)
[('1', '2'), ('1', '3'), ('2', '1'), ('2', '3'), ('3', '1'), ('3', '2')]

 

r개를 따로 뽑지 않으면 n개 만큼 순열 생성

>>> from itertools import permutations
>>> num = list(permutations(['1', '2', '3']))
>>> print(num)
[('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]

 

 

조합인 경우에는 combinations이용

import itertools
num = list(itertools.combinations(['1', '2', '3'], 2))
print(num)
[('1', '2'), ('1', '3'), ('2', '3')]

 

from itertools import permutations

n = int(input())
num_list = list(map(int, input().split()))
permu_list = list(permutations(num_list))   #모든 순열 리스트 만들기

max_value = -1

for permu in permu_list :                    #모든 순열 리스트에 있는거 하나씩 뽑아오기
    sum_num = 0
    for i in range(n-1) :
        num = abs(permu[i+1] - permu[i])
        sum_num += num
    if sum_num > max_value :                #차의 합 중 최대 합을 찾기
        max_value = sum_num

print(max_value)