백준 1461번: 도서관 (Java)

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

1461번: 도서관

 

 

 

 

 

 

 

 

---

 

풀이

주어진 책의 위치를 양수와 음수로 나눕니다(0은 입력으로 주어지지 않으니 고려하지 않아도 됩니다.). 양수의 개수를 a개, 음수의 개수를 b개라고 하면, 세준이는 모든 책을 갖다놓기 위해서 양수 쪽의 위치로는 math.ceil(a/m)번, 음수 쪽의 위치로는 math.ceil(b/m)번 이동해야 합니다. 한 번의 이동에 최대 M개의 책을 가져다 놓을 수 있는데, 끝 위치에서부터 M개를 채운다고 생각해봅시다.

문제의 예제 입력 1을 살펴보면,

2 11

-6 -28 -29 -37 -39

에 책을 가져다놓아야 합니다. M=2이므로, 양수 위치로는 최소 한 번, 음수 위치로는 최소 3번을 가야합니다. 양수/음수별로 끝 위치부터 2개씩 가져다놓는다고 생각하면,

11에 책 가져다 놓기

-39에 책 가져다 놓기

-29에 책 가져다 놓기

-6에 책 가져다 놓기

를 해야합니다. 여기서, 양수/음수 위치의 끝인 11과 -39를 살펴봅시다. 마지막에는 가져다 놓은 후 다시 책을 가지러 0에 가지 않아도 됩니다. 11보다 -39가 절댓값이 크므로, 세준이는 -39까지 가는 코스를 맨 마지막에 하여, -37, 그리고 -39에 책을 가져다 놓고 끝내면 됩니다. 즉, 양 끝 위치중 절댓값이 더 큰 곳은 한번만 더해주고, 나머지 방문은 *2를 해주어 더하면 총 걸음수가 나옵니다. 위 예제는, 11*2 + 6*2 + 29*2 + 39 = 131이 됩니다.

주어진 N이 작기에, 아마 그리디인줄 모르고 접했으면 그리디 풀이를 생각하지 못했을 듯 합니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        List<Integer> pos = new ArrayList<>();
        List<Integer> neg = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int cur = Integer.parseInt(st.nextToken());
            if (cur < 0) neg.add(-cur);
            else pos.add(cur);
        }
        Collections.sort(pos, Collections.reverseOrder());
        Collections.sort(neg, Collections.reverseOrder());
        
        int ans = 0;
        if (pos.isEmpty()) ans += neg.get(0);
        else if (neg.isEmpty()) ans += pos.get(0);
        else {
            ans += 2 * Math.min(pos.get(0), neg.get(0));
            ans += Math.max(pos.get(0), neg.get(0));
 
        }
        
        for (int i = M; i < pos.size(); i += M)    {
            ans += 2 * pos.get(i);
        }
        for (int i = M; i < neg.size(); i += M) {
            ans += 2 * neg.get(i);
        }
        System.out.println(ans);
    }
 
}