글 읽기 - 반례는 찾았는데.. 왜 틀렸는지 모르겠네요

uss425 3년 전 0

3 14

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

구멍이 남아있으면 그냥 꽂고, 남아있지 않으면

꽂혀있는 장치들중에서 앞으로 사용하지 않을 장치를 뽑거나, 가장 마지막에 쓰게 될 장치를 뽑는것 아닌가요?

아아아ㅏㅏ아ㅏㅏㅏㅏ

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

int n, k, mtap, ans=0; //n, k, 멀티탭 남은 칸 수, 정답
vector<int> schedule; //장치 사용 순서
vector<bool> check; //현재 멀티탭에 꼽혀 있는지? 
vector<int> cnt;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin>>n>>k;
	
	mtap=n;
	check.resize(k+1);
	cnt.resize(k+1);
	for(int i=0; i<k; i++)
	{
		int input;
		cin>>input;
		schedule.push_back(input);
		cnt[input]++;
	}
	
	for(int i=0; i<k; i++)
	{
		if(check[schedule[i]]) //schedule[i]가 이미 꽂혀 있는 경우 
		{
			cnt[schedule[i]]--;
			continue;
		}
		
		else if(mtap>0)  //구멍이 남아있는 경우 
		{
			check[schedule[i]]=true;
			mtap--;
			cnt[schedule[i]]--;
		}
		else //구멍이 남아있지 않은 경우 
		{	
			int minUse = 999; 
			int minUseIdx = 0;
			
			for(int j=1; j<=k; j++) 
			{
				if(check[j] && cnt[j]<minUse)
				{
					minUseIdx = j;
					minUse = cnt[j];
				}
			}
			
			if(minUse==0) //앞으로 사용하지 않을 장치라면, 
			{
				ans++;
				check[minUseIdx] = false;
				check[schedule[i]] = true;	
				cnt[schedule[i]]--;
				
				//cout<<minUseIdx<<" pop!\n";
			}
			
			//꼽혀있는 장치들 중에, 그런 장치가 없다면
			//가장 마지막에 쓸 장치를 뽑는다. 
			else  
			{
				for(int j=k-1; j>i; j--)
				{
					if(check[schedule[j]])
					{
						ans++;
						check[schedule[j]] = false;
						check[schedule[i]] = true;	
						cnt[schedule[i]]--;
						
						//cout<<schedule[j]<<" pop!\n";
						
						break;
					}
				}
			}
		}
		//cout<<schedule[i]<<" push!\n";
	}
	
	cout<<ans<<'\n';
	
	return 0;
}

leese0425 3년 전 4

꼭 마지막에 쓰이는 애를 뽑지는 않습니다!

2 15
3 2 1 2 1 2 1 2 1 3 3 3 3 3 3

답) 2

이 경우에

3 2가 꽂힌 상태에서 1을 꼽기 위해서 2를 빼는게 아니라 3을 빼야합니다.

그래서 마지막을 기준으로 생각하기 보다는, 다른 방법으로 생각 해 보세요!

uss425 3년 전 1

답변 감사합니다 (_ _)

꽂혀있는 장치들 중,

1. 앞으로 사용하지 않는 장치

2. 1.이 없다면, 가장 마지막에 쓸 장치

를 뽑는것 아닌가요..?? ㅜㅜ

+) 생일이 4월 25일이신가요?ㅋㅋ

leese0425 3년 전 3

구체적으로 말씀드리면 2.에서

가장 마지막에 쓸 장치라는 것이

다시 스케쥴링이 됐을 때 가장 마지막 순서로 스케쥴링이 되는 경우입니다.

현재 코드의 68번째 줄~부터는 현재 꽂혀있는 장치 중 마지막 순서로 스케쥴링이 되는 장치를 선택하는 것이 아니라

현재 꽂혀있는 장치 중 마지막까지 사용되는 장치를 선택하는 코드로 보입니다!

+)네 맞습니다 ㅎㅎ

uss425 3년 전 1

정말 큰 도움이 되었습니다 ㅜㅜ

군대 폰 제출 시간이라 leese님의 코드를 결국 못봤지만, 어떻게 어떻게 하다보니까 풀게되었어요!

그리디 공부 좀 더 하고, 다시 풀어야겠어요 ㅋㅋ

=> https://blog.naver.com/uss425/222014269782

다행히 싸지방 문 닫기전에 풀고 가네요 ㅎㅎ

다시 한번 감사합니다!

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

문제

문제

출처

ICPC

반례는 찾았는데.. 왜 틀렸는지 모르겠네요

uss425 3년 전 0

leese0425 3년 전 4

uss425 3년 전 1

leese0425 3년 전 3

uss425 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말