https://www.acmicpc.net/problem/10819
문제 풀이
[사용한 개념]
[시간복잡도]
1초 = 10^9
[permutation]
permutation(iterable, r)
- iterable : 순회할 수 있는 객체
- r: 몇 개를 뽑을 것인지
[종합 설명]
처음엔, 완전탐색이 아닌 다른 방법이 있을 수 있다고 생각했다. 그래서 다른 알고리즘적 방법을 생각해봤는데, 좋은 방법이 나오질 않았다. 그래서 다음에 풀어보아야겠다고 하며 넘어갔던 문제이다.
다시 봤을 땐, 완전탐색으로 풀릴 수 있는지 확인을 해보았다.
시간 복잡도 계산을 직접 해보았는데, n=8 이기 때문에 완전탐색을 해도 무방하였다!!
[계산]
1. permutation 만들기 : 8!
2. permutation 순회하기 & 매 permutation 객체마다 이웃 원소끼리의 차이 구하기 : 8! * 8
따라서, 총합은
8! + (8!*8)
= 40320 + 40320*8
= 362800
= 약 3*10^5
이다.
알고리즘 문제에서 1초에 10^9 연산을 처리할 수 있으므로, 통과되는 시간복잡도를 가진 코드였기에, 그대로 문제를 풀었다.
시간복잡도를 계산하는 방식을 적어두기 위해, 이 문제를 포스팅하게 되었다.
[코드]
from itertools import permutations
n = int(input())
nums = list(map(int,input().split()))
'''
1. 배열 나열하기
2. 각 배열마다의 값 구하기
'''
'''
<시간복잡도>
8! (= 40320)
+
8! * 8
=
362880 (= 3*10^5)
------------------
1초
10^9 까지 가능
'''
num_list = list(permutations(nums,n))
ans = -1
for i in range(len(num_list)):
hap = 0
for j in range(n-1):
hap += abs(num_list[i][j] - num_list[i][j+1])
ans = max(hap,ans)
print(ans)