[BOJ] 백준 1461 도서관 (C++)

문제 링크

www.acmicpc.net/problem/1461

1461번: 도서관

카테고리

그리디

문제 풀이

1. 양수, 음수 위치의 도서들을 분류해서 벡터에 저장한다.

2. 각각의 양수, 음수 도서들을 거리가 먼 순서로 정렬한다.
  👉 +, - 위치의 도서들을 섞어서 가져다 놓으면, 0을 여러번 지나게 되므로 최솟값이 나올 수 없다.

3. 최대로 들 수 있는 책의 개수 만큼 각각 묶음을 짓는다.
    3.1 각 벡터의 앞에서부터 묶고, 각 묶음의 첫번째 원소를 기준으로 2배씩 총 거리에 더해준다.
        👉 (그래야 해당 묶음의 모든 책들을 가져다 놓고 원점으로 올 수 있다.)
    3.2 가장 먼 위치의 책을 가장 나중에 가져다 놓아야 한다.

        👉 (다시 0으로 돌아갈 필요 없기 때문에)
        👉 3.1을 계산하면 가장 먼 책이 있는 그룹은 중복으로 더해지므로 총 거리에서 가장 먼 위치의 거리를 빼준다.

4. 계산된 최종 거리를 출력한다.

주의할 점

* 2개의 벡터로 분류해서 계산했으므로 가장 먼 거리에 있는 책의 거리를 구할 때 주의해야한다.

  (책의 거리가 모두 양수인 입력이나, 모두 음수인 입력이 주어질 때 각 벡터중 하나의 size가 0이 될 수도 있음.)

코드 (C++)

채점 결과

한마디

  책을 모두 제자리에 놔둔 후에는 돌아올 필요가 없다는 말을 보고 그리디로 풀어야함을 짐작했다.

  이런 힌트들을 잘 확인해 보는 습관을 꾸준히 들여야겠다. 🤔