[백준 1461][C++] 도서관

문제 링크

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

---

◆문제 해설 및 설명◆

 

문제 : 세준이는 책을 원래 자리에 놓아야 한다. 한 번에 M개의 책을 들 수 있다. 책들과 세준이의 시작 위치는 0이다.

책들의 위치는 세준이의 걸음을 기준으로 제공된다. 이때 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 구하라.

(단, 모든 책을 놓고 나서 0으로 돌아올 필요는 없다.)

 

이 문제는 그리디 알고리즘으로 풀었다.

 

예제 입력을 보기 쉽게 나타내면 아래 그림처럼 나온다.

예제 입력 1 추상화

세준이가 들 수 있는 책의 갯수가 1일 때, 각각 모든 위치에 가는 것(편도)을 계산하고 제일 먼 위치만 제외하고 x2를 해주었다. (갔다가 책을 가지러 다시 와야 하기 때문에 거리가 두 배가 된다.)

가장 큰 값을 제외한 이유는 그곳에 마지막에 가면 돌아올 계산을 안해도 되기 때문이다.

그래서 소요된 걸음은 다음과 같다.

2배 전

2배 후

그렇다면 세준이가 들 수 있는 책의 갯수가 2일 때는 어떨까?

책을 한권 놓고 다시 놓을 수 있으니, 가장 먼 거리를 가서 2권의 책을 놓는 것이 효율적일 것이다.

그럼 아래와 같이 걸음 수가 책정된다.

여기서 가장 큰 값을 빼고 2배를 해주고 더하면 총 걸음이 나온다.

2배 후

이와 같은 방법으로 매개변수에 따라 계산해 주는 방식으로 코드를 작성하였다.

 

◆코드 전문◆

#include <iostream>
#include <queue>
using namespace std;
void lenCal(priority_queue<int> &pr_que);
int N, M, answer = 0;
priority_queue<int> answerPQ;
priority_queue<int> pqP;
priority_queue<int> pqM;
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        int buf;
        cin >> buf;
        if (buf > 0)
        {
            pqP.push(buf);
        }
        else if (buf < 0)
        {
            pqM.push(-buf);
        }
    }

    lenCal(pqP);
    lenCal(pqM);

    answer += answerPQ.top();
    answerPQ.pop();
    while (!answerPQ.empty())
    {
        answer += answerPQ.top() * 2;
        answerPQ.pop();
    }
    cout << answer;
}

void lenCal(priority_queue<int> &pr_que)
{
    int count = 0;
    while (!pr_que.empty())
    {
        if (count % M == 0)
        {
            answerPQ.push(pr_que.top());
        }
        count++;
        pr_que.pop();
    }
}

 

책을 여러개 들 수 있을 때, 먼 거리를 가야 상대적으로 짧은 거리에 책을 추가 거리 없이 놓고 올 수 있기 때문에 큰 값이 top에 오는 우선순위 큐를 구현하였다.

양수와 음수를 구분하기 위해서 배열을 두개 선언해 주었고(pqP, pqM) 필요거리를 lenCal 함수를 통해 계산해 주었다.

(0과 M의 배수를 anwerPQ에 push 해주는 방식)

이후 anwerPQ에서 가장 긴 길이를 제외하고 2배하여 답을 도출하였다.