1461번: 도서관

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

 

---

그리디 문제다.

처음 문제를 보고, 음수와 양수를 나눠서 풀어야겠다는 생각이 들었다.

그리고, 음수, 양수 중 절댓값이 큰 수에 마지막으로 도착하도록 해야겠다는 생각도 해냈다.

왜냐하면 갔다가 다시 책을 가지기 위해 원점으로 돌아와야 하는데, 가장 큰 값에 도착했다가 다시 돌아온다면

절대 최솟값이 될 수 없기 때문이다.

 

이런 아이디어는 어떻게든 생각해내니 거의 1시간이 지나있었다.

구현해보다가 잘 안되어서 결국 풀이를 약간 참고해서 풀었다.

 

---

# 1461번: 도서관
# 음수와 양수를 나눠서 계산한다.
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))

plus_arr = []
minus_arr = []

for num in arr:
    if num > 0:
        plus_arr.append(num)
    else:
        minus_arr.append(-num) # 양수로 입력

plus_arr.sort(reverse=True) # 내림차순 정렬
minus_arr.sort(reverse=True) # 내림차순 정렬

total = 0 # 걷는 걸음 수의 총합

# 일단 m씩 건너 뛴 값의 2배를 추가
for i in range(0, len(plus_arr), m):
    total += plus_arr[i] * 2

# 일단 m씩 건너 뛴 값의 2배를 추가
for i in range(0, len(minus_arr), m):
    total += minus_arr[i] * 2

# 양수가 없다면, 음수에서 가장 절댓값을 마지막으로 도착한다.
# 그리고 다시 돌아오는 걸음이 필요 없으므로 빼준다.
if not plus_arr:
    total -= minus_arr[0]

# 음수가 없을 때도 동일하게 처리해준다.
elif not minus_arr:
    total -= plus_arr[0]
# 둘 다 있다면, 음수, 양수 중 절댓값이 가장 큰 값을 마지막을 도착한다.
# 해당 칸에서 다시 돌아오는 걸음이 필요 없으므로 빼준다.
else:
    total -= max(minus_arr[0], plus_arr[0])

print(total)

 

 

for문에서 k step을 활용하면 되는데 while 문으로 풀려고 하다보니 index out 에러가 계속 떠서 예외를 잘 못잡아서 구현하지 못했다.

그래도 아이디어는 좀 생각해낸게 장족의 발전을 이뤘다고 생각한다.

하루에 조금씩 계속 풀자!