글 읽기 - 27%에서 오류가 생깁니다 ㅠ

dhworhkd11 1년 전 0

모든 질문에 포함된 반례는 통과했는데

어떤 부분이 해결이 안되는지 모르겠네요..

코드 확인 반례 요청드리겠습니다 ㅠ

#pragma warning(disable:4996)
#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) {  // 다음으로 등장할 거리차에 대한 오름 차순 정리
	return a.second < b.second;
}

int main() {
	int N, K;
	int seq[101] = {};
	vector<pair<int,int>> box;       // 입력을 담을 벡터
	vector<pair<int,int>> pv;        // 멀티탭에 있는 기기 값을 담을 벡터
	scanf("%d %d", &N, &K);

	for (int i = 0; i < K; i++) {
		scanf("%d", &seq[i]);
	}

	for (int i = 0; i < K; i++) {
		int check = 1;                                      
		if(i!=K){  // pair로 담고 있음
			for (int j = i+1; j < K; j++) { // (등장한 시점 , 등장했던 시점 부터 다음 으로 등장할 같은 기기와의 거리 차)
				if (seq[i] == seq[j]) {                       
					box.push_back(make_pair(seq[i],(j - i)));          
					check = 0;
					break;
				}
			} 
		}
		else {
			check = 0;
		}
		if (check) box.push_back(make_pair(seq[i],111)); // 다음에 등장하지 않는 다면 거리차를 최대로
	}

	int sol = 0;

	for (int i = 0; i < K; i++) {
		int check = 1; // 멀티탭에 새로 꽃을지 않꽃을지 판단
		for (int j = 0; j < (int)pv.size(); j++) {  // 새로 들어오는 기기가 멀티탭에 이미 있는 기기 라면 다음으로 등장할 거리 값만 바꿔줌
			if (pv[j].first == box[i].first) {
				pv[j].second = box[i].second;
				check = 0;
				break;
			}
		}
		if(check){  // 꼽는다면
			if (N == pv.size()) { // 만약 멀티탭이 가득 차 있다면, 하나를 뽑을 껀데 가장 거리차가 큰 녀석을 뽑을 꺼임
				sort(pv.begin(), pv.end(), cmp);
				pv.pop_back(); // 가장 거리차가 큰 뒤에 있는 기기 뽑기
				sol++;
			}
			pv.push_back(box[i]); // 가득 차 있지 않은 상태라면 멀티탭에 꽃아주기
		}
		
	}

	printf("%d", sol);
	return 0;

}

byeongkeunahn 1년 전 5

그리디 전략이 적절하지 않습니다. 아래는 반례입니다.

4 20
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
-> should print 4, but prints 6

dhworhkd11 1년 전 0

감사합니다

다음 등장의 기기를 위한 현 시점에서의 남은 횟수를 구해줘야 하는군요

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

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

문제

문제

출처

ICPC

27%에서 오류가 생깁니다 ㅠ

dhworhkd11 1년 전 0

byeongkeunahn 1년 전 5

dhworhkd11 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말