[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());
}
}
오히려 시간도 단축되고 코드도 간결하다.
Author And Source
이 문제에 관하여([BOJ] 1461번 도서관), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@juijeong8324/BOJ-1461번-도서관저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)