글 읽기 - c++ 반례가 무엇일까요 ,,, ㅠㅠ

12dbwls34 3년 전 0

반례가 무엇일까요 ,, 질문에 올라와있는 반례는 해 본 결과 맞게 나오는데 제가 발견하지 못한 반례가 있을까요 ?!?!

감사합니다 ㅠㅠ

#include <iostream>
#include <vector>
using namespace std;

vector<int> arr, cnt(101, 0);
vector<bool> plug(101, 0);

int getSize() {
    int size = 0;

    for(int i = 0; i < plug.size(); i++) {
        if(plug[i]) {
            size++;
            // cout << i << " ";
        }
    }
    // cout << " size : " << size << "\n";
    return size;
}

int main() {
    int n, k, input, size = 0, answer = 0;
    cin >> n >> k;

    for(int i = 0; i < k; i++) {
        cin >> input;
        arr.push_back(input);
        cnt[input]++;
    }

    for(int i = 0; i < arr.size(); i++) {
        size = getSize();

        if(!plug[arr[i]]) {

            /*플러그에 비어 있는 자리 있는 경우*/
            if(size < n) {
                plug[arr[i]] = 1;
                cnt[arr[i]]--;
            } else {
                bool type = true;
                int index = -1;

                for(int j = 0; j < plug.size(); j++) {
                    if(plug[j] == 1 && cnt[j] == 0) {
                        type = false;
                        plug[j] = 0;
                        answer++;
                        plug[arr[i]] = 1;
                        cnt[arr[i]]--;
                        break;
                    }

                    if(plug[j] == 1 && cnt[j] != 0 && index < j) {
                        index = j;
                    }
                }

                if(type) {
                    plug[index] = 0;
                    answer++;
                    plug[arr[i]] = 1;
                    cnt[arr[i]]--;
                }

            }
        } else {
            cnt[arr[i]]--;
        }
    }

    cout << answer;


}

kth990303 3년 전 8

저랑 똑같은 반례에서 막혔군요

3 14
1 4 3 2 5 4 3 2 5 3 4 2 3 4

ans: 4

Wrong: 5

저도 현재 이렇습니다 ㅜㅜ 같이 잘 고쳐봐요

12dbwls34 3년 전 5

감사합니다! 제공해주신 반례로 해결했습니다!

플러그에 자리가 없고 꽂혀 있는 것들이 모두 나중에 사용해야할 것들인 경우가 가장 큰 문제였습니다.

(물론 제가 잘 못 작성한 부분도 있었어요!!)

제가 의도한 것은 무조건 제일 나중에 사용하게 되는 경우를 플러그에서 뽑고 새로운 것을 꽂아야 한다는 것 이였습니다.

그렇게 되면은 주신 반례에서 인덱스 값이 4인 5를 꽂는 경우에 문제가 발생합니다.

1 4 3

2 4 3

2 3 5 (4가 뽑히고 5가 꽂혀짐)

... 이렇게 콘센트가 꽂히게 되고 값이 결과값이 5가 됩니다!

하지만 최소로 플러그를 뽑으려면,

3 14

1 4 3 2 5 4 3 2 5 3 4 2 3 4

5 이후에 나오는 것 중에서

꽂혀있는 2는 index 7, 4는 index 5, 3은 index 6으로 가장 나중에 사용하게 될 2를 뽑아야합니다.

1 4 3

2 4 3

5 4 3 (2가 뽑히고 5가 꽂혀짐)

... 이렇게 되고 값이 4가 되어야 합니다.

따라서 저의 솔루션이 잘 못 된것임을 확인하였습니다 ㅠㅠ

덕분에 해결할 수 있었습니다!

감사합니다!

(제가 설명을 잘 못해서 도움이 될지는 모르겠네요 ㅠㅠ)

댓글을 작성하려면 로그인해야 합니다.