BOJ 1461 도서관

백준 BOJ 1461 도서관 C++

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

 

1) 단순 시뮬레이션 문제

2) 조건 "책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. " 를 이용해서
왼쪽/오른쪽 통틀어서 가장 큰 절댓값을 가진 위치를 마지막에 이동하는 것으로 생각하여 ans에 더한다.

3) 그 외 값들은 책을 두고, 다시 원점 0으로 돌아와야 하기 때문에

leftLoc[]에서 인덱스가 가장 큰 것의 배열값X2(왕복)을 ans에 더한 후, M만큼 인덱스를 감소했다.

마찬가지로 오른쪽(rightLoc[])도 인덱스가 큰 값에서부터 확인하여 ans에 더한 후, M만큼씩 인덱스를 이동했다.

4) 위치가 담긴 배열의 인덱스를 적절히 조작해서 계산하는 재미있는 문제였다.

 

/**
 * 200521
 * BOJ 1461 도서관
 * 시뮬레이션 : 왼쪽, 오른쪽 따로 관리한다.
 * */

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int leftLoc[10005];
int rightLoc[10005];
int leftIdx=0, rightIdx=0;
int leftMx=-1, rightMx=-1;

int ans = 0;

void leftCalc(){
    int idx = leftIdx-1;

    while(1){
        if(idx<0) break;
        ans += leftLoc[idx]*2;
        idx-=M;
    }
}

void rightCalc(){
    int idx = rightIdx-1;
    
    while(1){
        if(idx<0) break;
        ans += rightLoc[idx]*2;
        idx-=M;
    }
}

void solve(){
    if(leftMx >= rightMx){
        ans += leftLoc[leftIdx-1];
        leftIdx-=M;
    }
    else{
        ans += rightLoc[rightIdx-1];
        rightIdx-=M;
    }

    leftCalc();
    rightCalc();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;

    for(int i=0; i<N; i++){
        int x;
        cin >> x;
        if(x<0){ // 인풋이 음수일 때
            if(leftMx < abs(x)) leftMx = abs(x);
            leftLoc[leftIdx++] = abs(x);
        }
        else{ // 인풋이 양수일 때
            if(rightMx < x) rightMx = x;
            rightLoc[rightIdx++] = x;
        }
    }
    sort(leftLoc, leftLoc+leftIdx);
    sort(rightLoc, rightLoc+rightIdx);

    solve();
    
    cout << ans << '\n';
    return 0;
}