CAVEMAN. 전략의 오류인가요? 코딩의 오류인가요?

  • User Avatar
    iyaa

    https://algospot.com/judge/problem/read/CAVEMAN

    이 문제를 풀고 있습니다.

    현재 전략은, 다음과 같습니다. (예제 기준 설명)

    1 2 2 1 3 1 1 2 4
    이 input를 다음과 같이 변형합니다

    idx 0 1 2 3 4 5 6 7 8
    val 1 2 2 1 3 1 1 2 4

    after mutation
    (0,0) / (0,2) / (1,3) / (3,3) / (2,6) / (5,5) / (6,6) / (6,8) / (5,11)
    pair을 사용하여 저장한 후, sort 하면 다음과 같은 순서로 저장됩니다.

    (0,0) / (0,2) / (1,3) / (2,6) / (3,3) / (5,5) / (5,11) / (6,6) / (6,8)

    그 이후, 다음과 같이 선택합니다.
    ret=0
    처음 : 빛을 못받는 가장 좌측 인덱스 : 0 ret++
    (0,0) / (0,2) 중 (0,2) 선택,
    다음 : 빛을 못받는 가장 좌측 인덱스 : 3 ret++
    (1,3) / (2,6) / (3,3) 중 (2,6) 선택,
    다음 : 빛을 못받는 가장 좌측 인덱스 : 7 ret++
    (5,5) / (5,11) <- second value가 N-1 이상이므로 여기서 종료

    return ret합니다.

    이러한 로직 자체가 틀린것인지요? 코딩이 틀린것인지요?
    아래는 소스입니다.

    ~~~ c++
    #define _CRT_SECURE_NO_WARNINGS
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #define INF 987654321
    using namespace std;
    int solve(vector >& arr){
    sort(arr.begin(), arr.end());
    int next = -1;
    int mmax = 0;
    int ret = 0;
    int N = arr.size();
    for (int i = 0; i < N; i++){
    int left = arr[i].first;
    int right = arr[i].second;
    if (left > next){
    next = mmax;
    ret++;
    mmax = 0;
    }
    if (right > mmax){ mmax = right; }
    if (right >= N - 1){ break; }
    }

    return ret;

    }
    int main(){
    int T;
    cin >> T;
    while (T--){
    int N;
    cin >> N;
    vector > arr;
    for (int i = 0; i < N; i++){
    int buf;
    cin >> buf;
    int start = i - (buf - 1);
    int end = i + (buf - 1);
    arr.push_back(make_pair(start, end));
    }

        cout << solve(arr) << endl;
}
system("pause");

    }
    ~~~

    이 문제로 요며칠 고통받고있네요. 어디가 문제인지 알고싶습니다 ㅜㅜ


    10년 전
6개의 댓글이 있습니다.
  • User Avatar
    fleo0917

    left가 0보다 작은 경우 어떻게 될까요.


    10년 전 link
  • User Avatar
    iyaa

    @fleo0917
    그래서 left를 max(0,val)로도 해보았습니다만, 오답이 뜨는건 같았습니다 ㅜㅜ


    10년 전 link
  • User Avatar
    iyaa

    현재 알고리즘은 (0,0) / (0,2) / (0,5) 이런식일때 제대로 해결되지 않는 것 같아, 다음과 같이 코드를 바꿨습니다만 오류가 납니다.
    ~~~ c++
    #define _CRT_SECURE_NO_WARNINGS
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #define INF 987654321
    using namespace std;
    int solve1(vector >& board, int left, int right){
    int ret = 0;
    for (int i = left; i < right; i++){
    ret = max(ret, board[i].second);
    }
    return ret;
    }

    int solve2(vector >& board){
    int left = -1;
    int right = -1;
    int N = board.size();
    int ret = 0;
    int now = -1;
    int idx = 0;
    for (int i = 0; i < N; i++){
    if (now + 1 < board[i].first){
    ret++;
    cout << idx << " " << i << endl;
    now = solve1(board, idx, i);
    idx = i;
    if (now >= N - 1){ break; }
    }
    }
    return ret;
    }

    int main()
    {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--){
    int N;
    cin >> N;
    vector > board;
    for (int i = 0; i < N; i++){
    int buf;
    cin >> buf;
    int front = max(0, (i-(buf-1)));
    int end = i + (buf - 1);
    board.push_back(make_pair(front, end));
    }
    sort(board.begin(), board.end());
    board.push_back(make_pair(INF, INF));
    cout << solve2(board) << endl;
    }
    system("pause");
    }
    ~~~


    10년 전 link
  • User Avatar
    iyaa

    정정 -> 오류X, 오답입니다.


    10년 전 link
  • User Avatar
    kcm1700

    글에서 설명하신 알고리즘은 맞는 것 같네요. 구현이 정확하지 않은 것 같아요. 처음 글에서 올리신 코드의 next의 의미를 정확히 따져가면서 조건문과 답을 확정하는 순간이 맞는지 검토해보세요.
    right가 N-1보다 크거나 같으면 바로 break하는 부분에서 ret의 값과 선택한 것들의 개수가 같은지 따져보세요. 루프를 나왔을 때 선택한 것들로만 마지막까지 커버가 되었는지 따져보세요.


    10년 전 link
  • User Avatar
    iyaa

    @kcm1700
    답변 감사합니다! 말씀하신 부분 공부하다 그저께인가 깨닫고 풀었습니다.


    10년 전 link

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