[BOJ 1461, Python 3] 도서관

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

1461번: 도서관

 

풀이

예제가 단순한 예제였으면 풀기 엄청 힘들었을 것 같은 문제인데, 다행히도 예제가 문제를 푸는 아이디어를 이용해서 풀 수 있기 때문에 예제만 풀 수 있으면 쉽게 풀 수 있었던 문제입니다.

 

절댓값이 가장 큰 부호를 찾고, 그 큰 값부터 부호별로 내림차순으로 최대 m개씩 가져가면 됩니다. 절대값이 가장 큰 부호에서 처음 m개는 한 번만 더해주고, 나머지는 2를 곱해서 더해주면 됩니다.

 

그리고 이 문제는 경우의 수를 4가지로 나눌 수 있습니다.

1. 모든 수가 양수일 때

2. 모든 수가 음수일 때

3. 절댓값이 가장 큰 값이 음수이고, 음수 + 양수 섞여있을 때

4. 절댓값이 가장 큰 값이 양수이고, 음수 + 양수 섞여있을 때

 

1번과 2번 경우에는 정렬하여 절대값이 가장 큰 값에서 출발하여 처음 m개는 한 번만 답에 더해주고, 나머지는 2를 곱해서 답에 더해주면 됩니다.

3번의 경우에는 절댓값이 가장 큰 값이 음수이므로 음수에서 첫 m개를 한 번만 답에 더해주고, 양수와 음수 나머지는 2를 곱해서 답에 더하면 됩니다.

4번의 경우도 마찬가지로 양수에서 첫 m개를 한 번만 답에 더해주고, 양수와 음수 나머지는 2를 곱해서 답에 더해주면 됩니다.

 

1번 ~ 4번 전부 공통점은 부호 2개를 나누어서 내림차순으로 책을 m개씩 가져가는 거리들을 구하는 것입니다.

그래서 윗 줄을 미리 구해둬서 풀면 좀 더 깔끔하게 풀 수 있습니다.

 

 

 

코드

n, m = map(int, input().split())
arr = sorted([*map(int, input().split())])
plus = []
minus = []
for i in range(n):
    if arr[i] > 0: plus.append(arr[i])
    else: minus.append(arr[i])
 
plus_val = [plus[i] for i in range(len(plus) - 1, -1, -m)]
minus_val = [abs(minus[i]) for i in range(0, len(minus), m)]
 
plus_sum = sum(plus_val)
minus_sum = sum(minus_val)
 
if len(plus_val) == 0: print(2 * minus_sum - minus_val[0])
elif len(minus_val) == 0: print(2 * plus_sum - plus_val[0])
elif plus[-1] > abs(minus[0]): print(2 * (plus_sum + minus_sum) - plus_val[0])
else: print(2 * (plus_sum + minus_sum) - minus_val[0])