글 읽기 - 제가 어디서 잘못했는지 모르겠어요 도움 부탁 드려요 ㅠ

mineralwater 4년 전 0

set을 이용하여 멀티탭 상황을 업데이트 하고 있습니다.

1. 멀티탭이 비어있을 경우 지금 사용할 기기를 꽂음. (set에 넣음)

2. 지금 사용할 기기가 이미 멀티탭에 꽂혀있는 경우, 그냥 넘어갑니다. (continue)

3. 1,2번이 둘다 아닐경우

3-1. 꽂혀있는 모든 기기가 나중에 다시 사용될 경우, 제일 나중에 사용될 기기를 찾아서 빼고, 지금 사용할 기기를 꽂음.(플러그 빼는 횟수 +1)

3-2. 꽂혀있는 기기중에 나중에 다시 사용되지 않는 기기가 있을 경우, 그 중에서 아무거나 하나 빼고, 지금 사용할 기기를 꽂음.(플러그 빼는 횟수 +1)

이게 제 대략적인 생각이고, 게시판에 있는 반례는 다 테스트해봤습니다..

반례를 찾아주셔도 감사하고, 제 생각에 오류나 코드에 잘못된점을 지적해주셔도 감사합니다!!

#include <bits/stdc++.h>
using namespace std;

int N, K, A[105], ans; // ans = 플러그 빼는 횟수 (찾고자 하는 답)
set<int> s; // 멀티탭

int main() {
    cin >> N >> K;
    for(int i = 0; i < K; i++) cin >> A[i];

    for(int i = 0; i < K; i++) {
        if(s.size() < N) s.insert(A[i]); // 멀티탭이 비어있을경우
        else if(s.find(A[i]) != s.end()) continue; // 지금 사용할 기기가 이미 꽂혀있는 경우
        else {
            int cnt = 0;
            for(auto it = s.begin(); it != s.end(); it++) {
                for(int j = i + 1; j < K; j++) {
                    if(A[j] == *it) {
                        cnt++;
                        break;
                    }
                }
            }
            if(cnt == N) { // 꽂혀있는 모든 기기가 나중에 다시 사용될 경우
                int off = 0, idx = 0;
                for(auto it = s.begin(); it != s.end(); it++) {
                    for(int j = i + 1; j < K; j++) {
                        if(A[j] == *it && j > idx) { // 제일 늦게 사용되는 기기를 골라냄
                            idx = j;
                            off = A[j];
                        }
                    }
                }
                ans++;
                s.erase(off);
                s.insert(A[i]);
            }
            else { // 꽂혀있는 기기중에 나중에 다시 사용되지 않는 기기가 있을 경우
                for(auto it = s.begin(); it != s.end(); it++) {
                    int cnt1 = 0;
                    for(int j = i + 1; j < K; j++)
                        if(A[j] == *it) cnt1++;

                    if(cnt1 == 0) {
                        ans++;
                        s.erase(*it);
                        s.insert(A[i]);
                        break;
                    }
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

chw0501 4년 전 1

아이디어는 맞습니다.

하지만 cnt==N일 때 구현이 틀렸습니다.

현재 코드는

" 제일 늦게 사용되는 기기를 골라냄"

을 구현한 것이 아닌

"제일 늦게까지 사용되는 기기를 골라냄"

을 구현한 것입니다.

처음으로 사용되는 시점이 가장 나중인 기기를 빼야하는 것이죠.

mineralwater 4년 전 0

잘못된 부분 정확하게 찾아주셔서 덕분에 해결하였습니다 감사합니다~

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

문제

문제

출처

ICPC

제가 어디서 잘못했는지 모르겠어요 도움 부탁 드려요 ㅠ

mineralwater 4년 전 0

chw0501 4년 전 1

mineralwater 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말