[백준/Baekjoon] 1461 도서관 C++ :: Greedy

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

1461번: 도서관

---

728x90

1. Logic

- 0에서부터 왔다가 돌아와서 책을 다시 가져가야 하기 때문에 모든 (경로값 * 2)를 하게된다.  그렇기 때문에 입력을 모든 값중 절댓값이 가장 큰 경로에 있는 책을 제일 마지막에 가져다 놓아서 * 2를 하지 않아야겠다는 생각을 했다.

 

1, 양수를 저장하는 positive배열과 음수를 저장하는 negative 배열을 받아서 각각 저장하며 절댓값을 통해 절댓값이 가장 큰 값을 저장해놓는다.

 

가장 큰 값이 양수면 positive배열 중 가장 큰 값을 sum에 더한 상태토 나머지 수를 * 2를 하며 돌고

반대로 가장 큰 값이 음수면 negative배열 중 가장 작은 값을 sum에 더항 상태로 나머지 수를 * 2 해서 돌아준다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<int> positive;
vector<int> negative;

int main() {
    int n, m;
    
    cin >> n >> m;

    int ex = 0;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;

        if(abs(ex) < abs(a)) {
            ex = a;
        }

        if(a > 0)
            positive.push_back(a);
        else if(a < 0)
            negative.push_back(a);
    }

    sort(negative.begin(), negative.end());
    sort(positive.begin(), positive.end(), greater<>());

    if(ex > 0) {
        int sum = ex;

        for(int i = m; i < positive.size(); i+=m) {
            sum += positive[i] * 2;
        }

        for(int i = 0; i < negative.size(); i+=m) {
            sum += abs(negative[i] * 2);
        }
        cout << sum;
    }
    else if(ex < 0) {
        int sum = abs(ex);
        for(int i = 0; i < positive.size(); i+=m) {
            sum += positive[i] * 2;
        }

        for(int i = m; i < negative.size(); i+=m) {
            sum += abs(negative[i] * 2);
        }

        cout << sum;
    }
}

 

 

---

 

 

3. Feedback

이번 문제는 아이디어 생각하는데에 시간을 30분정도 쏟았지만 구현이 어렵지 않아서 내 기준 나쁘지 않게 풀은 것 같다.