백준 1461번 파이썬

문제 링크 : https://www.acmicpc.net/problem/1461

 

구현

N, M = map(int, input().split())
arr = list(map(int, input().split()))

# 양수와 음수 분리
pos = []
neg = []

for i in arr:
	if i > 0:
		pos.append(i)
	else:
		neg.append(-i)

# 내림차순 정렬
pos.sort(reverse=True)
neg.sort(reverse=True)

dists = []
for p in pos[::M]:
	dists.append(p)

for n in neg[::M]:
	dists.append(n)

answer = 2 * sum(dists) - max(dists)
print(answer)

• 그리디 알고리즘 활용

 

---

풀이

# 양수와 음수 분리
pos = []
neg = []

for i in arr:
	if i > 0:
		pos.append(i)
	else:
		neg.append(-i)

• 양수는 양수 끼리, 음수는 음수끼리 묶어 가는게 효율적 -> 양수와 음수 배열을 따로 만들어 줌

 

# 내림차순 정렬
pos.sort(reverse=True)
neg.sort(reverse=True)

• 먼 곳부터 갔다오는게 효율적 -> 각 배열을 내림차순해줌.

 

dists = []
for p in pos[::M]:
	dists.append(p)

for n in neg[::M]:
	dists.append(n)

answer = 2 * sum(dists) - max(dists)

• 한 번에 가지고 올 수 있는 책의 수 (M)만큼 만 배열에 담아줌 -> 왔다 1번 갔다 1번 2번이라서 2를 곱해주지만 가장 먼곳은 1번이라서 전체적으로 2를 곱해주고 가장 먼거리를 한번 빼주는 방식으로 풀이.

 

---

 

(+) 배열 슬라이스 

list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

list[:]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# 주로 배열을 복사할 때 사용

list[::3]
# [0, 3, 6, 9]
# 3씩 건너뜀 

list[::-1]
# [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
# 역순으로 정렬