[BOJ] 1461번 도서관

도서관 << 문제 클릭!

✅문제 설명

세준이와 책들의 위치가 0이다. 책들의 원래 위치가 주어질 때 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산해라.

• 입력
  : 책의 개수 N, 한 번에 들 수 있는 책의 개수 M (1 <= N,M <= 50)
  : 책의 위치 (0 없음, 절댓값은 10,000보다 작거나 같은 정수)

• 출력
  : 최소 걸음 수

• 조건
  : 1 걸음 = 좌표 1칸
  : 책의 위치는 모두 정수
  : 책을 모두 제자리에 놔두면 다시 0으로 돌아올 필요가 없다. == 가장 거리가 먼 위치는 돌아오지 않아도 된다.

❗핵심원리

• Greedy Algorithm 참고자료
  : 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만 쫓는 것.
  : 그 순간에 대해 지역적으로 최적이지만 최종적인 선택에서는 최적이라는 보장이 없다!
  => 따라서 그리디 알고리즘을 적용하려면 지역적으로 최적이면서 전역적으로 최적인 문제!!
  : 앞의 선택이 이후의 선택에 영향을 주치 않아야 하며 부분 문제에 대한 최적해는 전체 문제에 대한 최적해가 되어야 한다.

• 원리

  

: 세준이가 책을 한 번 두는데 왕복한다 == 가장 거리가 먼 곳은 왕복하면 안 된다.
: 세준이가 책을 한 번 두는데 거리가 먼 곳을 기준으로 왕복한다.
== 이때 책의 개수가 M권을 기준으로 왕복한다.
== 이때 책의 위치가 적은 곳 부터 왕복하는 것은 그리디가 아니다.

✅ 한 번 책을 두는데 가장 거리가 먼 곳 부터 M개 씩 책을 정리

💻코드

• 양수 부분과 음수 부분을 나누어서 절댓값 거리가 큰 것부터 더하는 것이 포인트!
• vector의 begin(), end()는 iterator고 front(), back()은 해당 원소를 반환한다는 것을 기억하자~

1차

include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    vector<int> pos; // 양수 배열
    vector<int> neg; // 음수 배열 
    int sum = 0;

    int temp = 0;
    for (int i = 0; i < N; i++) {
        cin >> temp;
        if (temp > 0) {
            pos.push_back(temp); // 양수 추가
        }
        else {
            neg.push_back(temp); // 음수 추가 
        }
    }

    sort(neg.begin(), neg.end()); // 오름차순 
    sort(pos.begin(), pos.end());   

    int i = 0;
    while (i < neg.size()) {
        sum -= 2*neg[i]; // 절댓값을 더해줘야 하니까
        i += M; // M만큼 증가 
    }

    int j = pos.size()-1; // 인덱스는 i-1번째니까
    while (j > 0) {
        sum += 2*pos[j]; // 더해줌 
        j -= M;
    }

    if (-neg.front() > pos.back()) { 
        cout << sum + neg.front();
    }
    else {
        cout << sum - pos.back();
    }

    return 0;
}

✅문제 원인
예제 중 1 50 1인 경우를 테스트 해보니 다음과 같은 에러가 떴다.
즉, empty vector의 front()를 호출하고 있다는 것!

물론 if와 else를 이용해서 문제를 해결할 수 있지만, 효율적이지 않다는 판단하게 코드를 바꾸기로 했다.

2차

• 굳이 양수와 음수로 나누지 않고 한 벡터에서 계산
• 음수의 개수를 count 함

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    vector<int> v; // 전체 배열 
    int sum = 0;
    int temp = 0;
    int count = 0;

    for (int i = 0; i < N; i++) {
        cin >> temp; 
        v.push_back(temp); // 양수 추가
        if (temp < 0) {
            count++; // 음수 개수 count 
        }
        
    }
    sort(v.begin(), v.end()); // 내림차순

    for (int i = 0; i < count; i += M) {// M만큼 증가 
        sum -= 2*v[i]; // 절댓값을 더해줘야 하니까
    }

     // 인덱스는 i-1번째니까
    for(int i = v.size()-1; i>= count;i -= M){
        sum += 2 * v[i]; // 더해줌 
    }

    if (abs(v.front()) < abs(v.back())) { //절댓값으로 바로 비교 
        cout << sum - abs(v.back());
    }
    else {
        cout << sum - abs(v.front());
    }

}

오히려 시간도 단축되고 코드도 간결하다.