[C++] BOJ 2184: 김치 배달

 

 

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

문제

월드 식품에서는 김치를 만들어 여러 도시들에 배달 판매하는 일을 하고 있다. 각각의 도시들과 김치 공장은 1차원 직선상의 점에 위치해 있다. 각 도시는 정수 좌표로 나타난다.

배달을 할 때에는 공장에서 $N$($1 \leq N \leq 1{,}000$)포기의 김치를 들고 시작한다. 그리고 1차원 직선을 따라 왼쪽이나 오른쪽으로 움직인다. 이동을 할 때에는 $1$초에 한 칸씩 움직일 수 있다. 또한 어떤 도시에 도착했을 때 김치는 $0$의 시간에 배달되는 것으로 생각한다. 즉 도시에 도착하기만 하면 배달이 완료되는 것으로 생각한다. 또한 김치를 배달하는 순서는 상관이 없다.

각각의 김치는 모두 $t=0$ 의 시각에 공장에서 출발된다. 각각의 김치는 $1$초에 $1$만큼씩 쉬게 되는데, 김치가 쉬게 될 경우 소비자가 불만을 토로할 수 있다. 따라서 월드 식품에서는 각 도시에 김치가 도착했을 때의 김치의 쉰 정도의 합을 최소로 하려 한다.

각 도시의 위치 및 김치 공장의 위치(x좌표)가 주어졌을 때, 모든 도시에 김치를 배달할 때의 김치의 쉰 정도의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 $N$, $L$이 주어진다. $L$은 김치 공장의 x좌표이다. 다음 N개의 줄에는 김치를 배달할 도시의 x좌표가 주어진다. 모든 좌표는 $1$이상 $1{,}000{,}000$이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

---

 

 

[C++] BOJ 2419: 사수아탕

[C++] BOJ 2419: 사수아탕

 

풀어놨던 사수아탕과 매우 유사했기에 바로 풀어봤다.

막힌 점은 $N$의 제한 정도? 메모리 제한과 시간 제한을 최적화 한 것 밖에 없다.

심지어 메모리 제한은 몰라도 시간 제한은 break 하나만 추가해줬는데 AC받았다...

다만 시간이 1.7초나 걸려버렸다.

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

using namespace std;

int N, l;
vector <int> homes;

long long L[1005][1005][2];
long long R[1005][1005][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> l;
    for(int i = 0; i < N; i++) {
        int x; cin >> x;
        homes.push_back(x);
    }
    
    N++; homes.push_back(l);
    
    sort(homes.begin(), homes.end());
    
    int s = 0;
    while(homes[s] != l) s++;
    
    long long mn = 1e18;
    int before = 0, current = 0;
    for(int k = 1; k < N; k++) {
        before = current;
        current = (current + 1) % 2;
        
        for(int i = 0; i < N; i++) {
            for(int j = i; j < N; j++) {
                L[i][j][current] = R[i][j][current] = 1e17;
                if(k > N - (j - i + 1)) break;
                
                if(i > 0) {
                    L[i][j][current] = min(L[i][j][current], L[i-1][j][before] + k * (homes[i]-homes[i-1]));
                    R[i][j][current] = min(R[i][j][current], L[i-1][j][before] + k * (homes[j]-homes[i-1]));
                }
                if(j < N - 1) {
                    L[i][j][current] = min(L[i][j][current], R[i][j+1][before] + k * (homes[j+1]-homes[i]));
                    R[i][j][current] = min(R[i][j][current], R[i][j+1][before] + k * (homes[j+1]-homes[j]));
                }
            }
        }
    }
    
    cout << L[s][s][current] << "\n";
    return 0;
}