DARPA 문제 문의 드립니다.

  • sancho
    sancho

    DARPA 문제 풀다 막혀서.. 글을 남깁니다.
    책에서는 결정문제 풀이 밖에 없어서
    동적계획법으로 풀어보고 있습니다.

    m개의 카메라 중계소에 n개의 카메라를 설치하는 방법은
    mCr 이므로, 먼저 조합을 생성하는 재귀 호출을 작성했습니다.
    사전 순서대로 조합을 생성하도록 만들고,
    아래 코드와 같이 메모이제이션을 적용하였습니다.

    예제입력 및 제가 만든 TC는 제대로 동작하는데 자꾸 오답으로 나오네요.
    실수처리가 잘못되었나 해서 의심가는 부분은 모두 소수점을 붙였고..
    다른 하나의 의심점은 메모이제이션하는 부분인데, 제 생각이 틀린건지요.

    미리 감사드립니다.

    #include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

const float INF = 987654321.0;
float LOCATION[200];
float CACHE[201][201];

void init()
{
    for (int i = 0; i < 201; i++)
        for (int j = 0; j < 201; j++)
            CACHE[i][j] = -INF;
}

float solve(vector<int>& picked, int m, int n)
{
    if (n == 0) {
        if (picked.size() < 2) return 0.0;
        float ret = INF;
        for (int i = 1; i < picked.size(); i++)
            ret = min(ret, LOCATION[picked[i]] - LOCATION[picked[i - 1]]);
        return ret;
    }
    int next = picked.empty() ? 0 : picked.back() + 1;
    float& ret = CACHE[next][n];
    if (ret != -INF) return ret;
    ret = 0.0;
    for (int i = next; i < m; i++) {
        picked.push_back(i);
        ret = max(ret, solve(picked, m, n - 1));
        picked.pop_back();
    }
    return ret;
}

int main(int c, char **v)
{
    ios_base::sync_with_stdio();
    int C;
    cin >> C;
    while (C--) {
        int m, n;
        cin >> n >> m;
        init();
        for (int i = 0; i < m; i++)
            cin >> LOCATION[i];
        vector<int> picked;
        cout << fixed << setprecision(2) << solve(picked, m, n) << endl;
    }
    return 0;
}


    8년 전
4개의 댓글이 있습니다.
  • JongMan
    JongMan

    처리하지 않으신 기저 사례가 있는 것 같습니다.

    (n 이 아직 남아 있는데, next=m인 경우)


    8년 전 link
  • sancho
    sancho

    종만님, 답변 감사드립니다.

    말씀하신 기저 사례는 이미 고려되고 있다고 생각하는데요.
    next == m일 경우에 ret = 0.0 인 상태로 for문의 조건에 걸리지 않고
    그대로 리턴되어 재귀호출이 실행되지 않습니다.


    8년 전 link
  • JongMan
    JongMan

    아, 제가 헷갈렸네요. 해당 경우 저는 INF를 반환해야 한다고 생각했는데 아니었군요.

    동적 계획법을 구현하신 방법에 문제가 있습니다. next와 n을 키로 사용하셨는데, next와 n이 모두 같아도 답이 다른 경우가 있습니다. picked 때문입니다. picked에 들어가 있는 카메라의 위치들이 {0, 1, 100, 200} 인 경우와 {0, 50, 100, 200} 인 경우를 생각해 보세요. 그러면 남은 장소와 카메라의 개수는 같지만, 기저 사례에서 picked를 순회하며 최소 차이를 찾기 때문에 전자는 무조건 1 이하의 값을 리턴하게 됩니다.

    이런 이유로 동적 계획법은 대개 주어진 위치 이후만을 다루는 부분 문제의 최적해를 반환하는 형식으로 구현하셔야 합니다.


    8년 전 link
  • sancho
    sancho

    네 음.. 근본부터 틀렸군요.
    더 생각을 해봐야 겠네요ㅎㅎ
    답변 감사드립니다.


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.