[BOJ] 백준 1461. 도서관

문제

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

---

풀이

정렬을 포함한 구현 문제이다. 처음에는 방문 배열을 적용해 탐색을 해야하나 싶었지만, 다시금 아이디어를 떠올려보니 단순 구현으로 해결될 것 같았다.

 

"세준이가 한 번에 들 수 있는 책"을 보고, 가지고 있는 책의 매개변수를 관리해야하나 싶었는데, 여기서 책의 숫자는 배열상 인덱스 거리와 같기 때문에 단순 배열에서의 거리 이동으로 구현했다.

 

 아이디어는 우선 center를 구한다. center는 세준이가 돌아오는 기점이면서 책을 충전하는 곳이다. 그러기 위해 배열을 입력받을 때 0 인덱스 위치를 포함시켰다. 배열을 정렬하고 값이 0인 인덱스 위치를 저장한다.

 

 

그리고 책을 놓으러 다닌다. 여기서 핵심 아이디어는 0에서 가장 멀리 떨어진 값만 한번 이동하고 나머지는 모두 2번씩 이동하면 된다. 그리고 이동시에는 책의 개수 M만큼 점프하면서 이동한다. 이동의 시작점은 양 끝 값이다!

 

(만약 0부터 시작하게 되면 홀짝과 M에 따라 로직이 따로 처리되어야하기 때문에 양 끝에서 시작하는 것이 수월하다)

 

 

아래는 소스 코드이다.

---

소스 코드

import java.util.Arrays;
import java.util.Scanner;

public class B1461_도서관 {
    static int[] loc;
    static int N, M, steps;
    static int center = -1;

    public static void main(String[] args) {
        input();
        Arrays.sort(loc);
        findCenterIndex();
        fillBook();
        System.out.println(steps);
    }

    static void fillBook(){
        steps = 0;
        int left = 0;
        int right = N;

        while(left<center){
            if(left==0&&Math.abs(loc[0])>=Math.abs(loc[N])){
                steps+=Math.abs(loc[left]);
            }
            else steps+=2*Math.abs(loc[left]);
            left+=M;
        }

        while(right>center){
            if(right==N&&Math.abs(loc[0])<Math.abs(loc[N])){
                steps+=Math.abs(loc[right]);
            }
            else steps+=2*Math.abs(loc[right]);
            right-=M;
        }
    }

    static void findCenterIndex(){
        for(int i = 0; i<=N; i++){
            if(loc[i]==0) center = i;
        }
    }

    static void input(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        loc = new int[N+1];
        for(int i = 0; i<N; i++){
            loc[i] = sc.nextInt();
        }
        loc[N] = 0;
    }
}