algospot.com :: 질문과 답변: CAVEMAN. 전략의 오류인가요? 코딩의 오류인가요?

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

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합니다.

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

#define _CRT_SECURE_NO_WARNINGS
#include<cstring>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
#define INF 987654321
using namespace std;
int solve(vector<pair<int, int> >& 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<pair<int, int> > 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");
}

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

8년 전

6개의 댓글이 있습니다.

fleo0917

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

8년 전 link
iyaa

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

8년 전 link

iyaa

현재 알고리즘은 (0,0) / (0,2) / (0,5) 이런식일때 제대로 해결되지 않는 것 같아, 다음과 같이 코드를 바꿨습니다만 오류가 납니다.

#define _CRT_SECURE_NO_WARNINGS
#include<cstring>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
#define INF 987654321
using namespace std;
int solve1(vector<pair<int, int> >& 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<pair<int, int> >& 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<pair<int, int> > 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");
}

8년 전 link

iyaa

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

8년 전 link
kcm1700

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

8년 전 link
iyaa

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

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

SINCE 2007

다가오는 이벤트들

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

6개의 댓글이 있습니다.