BOJ_1461 C++

HDuckkk·2023년 3월 16일

Beakjoon Online Judge

목록 보기

7/13

BOJ 1461 도서관

문제
세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

풀이과정

위의 문제는 그리디 사고방식으로 접근하여 해결했다.

결국 이동거리가 짧아지기 위해서는 가장 먼 곳을 제외하고는 최대한 많은 책을 들고 멀리까지 나가는 것이 제일 유리하다.

여기서 가장 먼 곳을 제외하는 이유는 문제의 조건 중 책을 모두 제자리에 놔둔 후에는 다시 돌아올 필요가 없다는 조건이 명시되어 있기 때문이다.

즉, 굳이 가장 먼 거리를 왕복할 필요가 없다는 것이다.

문제의 요점을 다시 잡아보자.

가장 먼 거리를 제외하고는 최대한 많은 양의 책을 들고 멀리까지 움직인다.
반대 방향으로는 움직일 수 없어야한다.

이후 책과 펜을 들고 여러 방식을 고민해 보았는데, 가장 괜찮았던 방식이 책을 갖다두는 모든 왕복 거리를 계산한 다음 가장 먼 곳의 위치한 책을 가져다 두는 편도의 거리를 뻬주는 방식으로 진행했다.

이후 코드를 보며 설명을 이어나가겠다.

초기화

void INIT(){
    for(int i=0; i<N; i++){
        int _x;
        cin >> _x;

        vec.push_back({abs(_x), _x});
    }
    sort(vec.begin(), vec.end());
}

위의 함수는 책이 돌아가야할 위치의 좌표와 거리를 넣어줄 벡터를 초기화 하는 함수이다. 여기서 거리만을 입력하는 것이 아닌 좌표까지 입력하는 이유는 반대방향으로 움직이는 연산을 if continue 문을 통해 막기 위함이다.

Solution

void gready(){
    INIT();

    int maxDistance = 0;
    int ans = 0;

    while(1){
        int loc = 0;
        int distance = 0;
        for(int j=vec.size()-1; j>=0; j--){
            if(vec[j].first == 0) continue;
            
            loc = vec[j].second;
            distance = vec[j].first;

            vec[j] = {0,0};
            break;
        }
        
        if(distance == 0) break;

        for(int j=1; j<M; j++){
            for(int k=vec.size()-1; k>=0; k--){
                if(vec[k].first==0) continue;
                if(loc > 0 && vec[k].second < 0) continue;
                if(loc < 0 && vec[k].second > 0) continue;

                vec[k] = {0,0};
                break;
            }
        }
        maxDistance = max(maxDistance, distance);
        ans += (distance * 2);
    }

    cout << ans - maxDistance;
}

총 코드

// BOJ 1461
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
using namespace std;
using pii = pair<int, int>;

int N, M;
vector<pii> vec;

void INIT(){
    for(int i=0; i<N; i++){
        int _x;
        cin >> _x;

        vec.push_back({abs(_x), _x});
    }
    sort(vec.begin(), vec.end());
}

void gready(){
    INIT();

    int maxDistance = 0;
    int ans = 0;

    while(1){
        int loc = 0;
        int distance = 0;
        for(int j=vec.size()-1; j>=0; j--){
            if(vec[j].first == 0) continue;
            
            loc = vec[j].second;
            distance = vec[j].first;

            vec[j] = {0,0};
            break;
        }
        
        if(distance == 0) break;

        for(int j=1; j<M; j++){
            for(int k=vec.size()-1; k>=0; k--){
                if(vec[k].first==0) continue;
                if(loc > 0 && vec[k].second < 0) continue;
                if(loc < 0 && vec[k].second > 0) continue;

                vec[k] = {0,0};
                break;
            }
        }
        maxDistance = max(maxDistance, distance);
        ans += (distance * 2);
    }

    cout << ans - maxDistance;
}

int main(){

    cin >> N >> M;

    gready();

    return 0;
}