Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
Tags
- 가상메모리
- 힙
- 프로그래머스
- level2
- BOJ
- 다이나믹 프로그래밍
- 파이썬
- 구현
- 스택
- BFS
- dfs
- 백준
- 그리디
- level0
- 가상메모리 관리
- 재귀
- 운영체제
- DP
- 브루트포스
- 다익스트라
- dict
- 코딩테스트
- 수학
- N과M
- level3
- 딕셔너리
- python
- programmers
- level1
- MYSQL
Archives
- Today
- Total
동캄의 코딩도장
백준 10819 [차이를 최대로] 파이썬 본문
https://www.acmicpc.net/problem/10819
10819번: 차이를 최대로
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
www.acmicpc.net
import sys
input = sys.stdin.readline
N = input().rstrip()
sum = 0
answer = 0
lst = list(map(int, input().split()))
lst.sort()
slst = lst[:len(lst)//2]
lst = lst[len(lst)//2:]
i = -1
for i in range(len(slst)-1):
sum += lst[i]-slst[i]
sum += lst[i+1]-slst[i]
i += 1
sum += lst[i]-slst[i]
if len(lst) != len(slst):
sum += lst[i+1]-slst[i]
answer = max(sum, answer)
sum = 0
lst.append(lst.pop(0))
i = -1
for i in range(len(slst)-1):
sum += lst[i]-slst[i]
sum += lst[i+1]-slst[i]
i += 1
sum += lst[i]-slst[i]
if len(lst) != len(slst):
sum += lst[i+1]-slst[i]
answer = max(sum, answer)
print(answer)
다음과 같은 방식으로 문제를 해결하려고 하였으나, 예외 케이스가 발생하여서 실패했다 ㅠㅠ
#10819
import sys, itertools
# 입력
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
# 순열
permu = itertools.permutations(data, n)
# 차이가 최대인 값을 넣을 변수
answer = 0
for p in list(permu):
# 차이의 합을 저장하는 임시 변수
sumNum = 0
# 차이의 합 계산
for i in range(n-1):
sumNum += abs(p[i]- p[i+1])
# 차이의 합 최대값 비교
if sumNum > answer: # answer = max(sumNum, answer) - 실행시간이 더 걸림
answer = sumNum
print(answer)
다른분의 풀이를 참고하여 해결하였다.
순열을 이용하여 모든 경우의 수를 체크해본다.
'코테 > BOJ' 카테고리의 다른 글
백준 14501 [퇴사] 파이썬 (0) | 2022.02.09 |
---|---|
백준 1759 [암호만들기] 파이썬 (0) | 2022.02.09 |
백준 11724 [연결 요소의 개수] 파이썬 (0) | 2022.02.08 |
백준 1260 [DFS와 BFS] 파이썬 (0) | 2022.02.08 |
백준 12865 [평범한 배낭] 파이썬 (0) | 2021.12.15 |