[1일 1알고] G4 16169 수행 시간

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

---

개요

    1. 1~n개의 컴퓨터가 존재, 컴퓨터는 계급, 동작 속도를 가짐 > 0
    2. i<->j의 전송 시간 = (i-j)^2
    3. 계급은 ci, 오름 차순으로 정리한다면 |c(j)-c(j-1)|<=1 -> 1보다 크게 차이나지 않음
    4. 최하위 계급을 제외한 컴퓨터는 한 단계 낮은 계급에게 "모두"전달받아야 동작 가능
    5. 최하위 컴퓨터는 시동과 동시에 동작
    6. c계급 컴퓨터가 동작을 마치면 "모든" c+1컴퓨터에 정보 전달 후 종료

+ 가장 낮은 계급이 1

위의 조건이 필요합니다.

 

처음에는 하나의 컴퓨터가 종료 후 다음 계급 컴퓨터 하나에 전달한다고 오해해 시간이 걸렸지만

모두 전달받아야하며, 종료 시 모든 곳에 전달한다는 것을 이해하니 문제가 풀렸습니다.

---

풀이

using namespace std;

struct computer
{
    int c, t; // 계급, 동작 속도
    int idx, res; // 인덱스, 동작 후 시간
};

bool cmp(const computer& a, const computer& b)
{
    return a.c < b.c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    /* 
    1. 1~n개의 컴퓨터가 존재, 컴퓨터는 계급, 동작 속도를 가짐 > 0
    2. i<->j의 전송 시간 = (i-j)^2
    3. 계급은 ci, 오름 차순으로 정리한다면 |c(j)-c(j-1)|<=1 -> 1보다 크게 차이나지 않음
    4. 최하위 계급을 제외한 컴퓨터는 한 단계 낮은 계급에게 전달받아야 동작 가능
    5. 최하위 컴퓨터는 시동과 동시에 동작
    6. c계급 컴퓨터가 동작을 마치면 c+1에 정보 전달 후 종료
    */

    int n;
    cin >> n;

    vector<computer> v(n);

    for (int i = 0; i < n; ++i)
    {
        cin >> v[i].c >> v[i].t;
        v[i].idx = i;
        v[i].res = 0;
    }

    sort(v.begin(), v.end(), cmp);

    for (int i = 0; i < n; ++i)
    {
        v[i].res += v[i].t; // 동작 시간 계산
        for (int j = i+1; j < n; ++j)
        {
            if (v[i].c + 1 == v[j].c)
            {
                v[j].res = max(v[j].res, 
                    v[i].res + (v[i].idx - v[j].idx) * (v[i].idx - v[j].idx)); // 이전 시간 + 전송 시간
            }
            else if (v[i].c + 1 < v[j].c)
                break;
        }
    }

    int ans = 0;
    for (int i = 0; i < n; ++i)
        ans = max(ans, v[i].res);

    cout << ans;
    return 0;
}

필요한 정보가  계급c와 동작시간t 그리고 컴퓨터의 위치(인덱스) + 현재 실행시간이라고 생각해서 별도로 구조체를 만들었습니다.

 

또한 2이상의 계급을 가지는 컴퓨터는 모든 c-1계급의 컴퓨터에 전달받은 후에야 실행될 수 있기 때문에 최적화를 위해 c기반으로 정렬했습니다.

 

그리고 c+1계급의 컴퓨터가 시작할 수 있는 시간은 c계급 컴퓨터가 동작을 마친 시간 + 전송 시간의 최대이기 때문에 이를 계산했습니다.

 

그리고 2단계 이상의 차이는 계산할 필요가 없기 때문에 커팅했습니다.

 

마지막으로 벡터를 순회하며 최대로 걸린 시간이 모든 컴퓨터가 동작을 마친 시간이기 때문에 이를 출력했습니다.

---

 예시에서는 마지막 계급의 컴퓨터가 하나이기 때문에 마지막 컴퓨터를 출력하려는 실수만 안하면 될 것 같습니다.

 

추가적으로 최댓값을 미리 계산하거나 마지막 계급이 시작하는 인덱스를 저장하면 조금 더 최적화할 수 있겠네요.

지금도 충분해서 하지는 않았습니다.