글 읽기 - 2565 전기줄 문제 반례 부탁드립니다!!!!!

dlftls38 7년 전 1

그리디로 짠건데요

정말 제가 왠만한 예제 다해본결과 다 맞게나오는데 뭐가 문제일까요...!!!!!

제발 부탁드립니다

#include <stdio.h>
int main(){
	int n;
	int i,j;
	scanf("%d",&n);
	int a[510]={0};
	for(i=0;i<n;i++){
		int q,w;
		scanf("%d%d",&q,&w);
		a[q]=w;
	}
	int count[510]={0};
	int something[510][100]={0};
	int top[510]={0};
	for(i=2;i<510;i++){
		for(j=1;j<i;j++){
			if(a[i]<a[j] && a[i]!=0){
				count[i]++;
				count[j]++;
				something[i][top[i]]=j;
				top[i]++;
				something[j][top[j]]=i;
				top[j]++;
			}
		}
	}
	int result=0;
	for(i=0;i<200;i++){
		int max=0;
		int index=0;
		for(j=0;j<510;j++){
			if(max<count[j]){
				max=count[j];
				index=j;
			}
		}
		if(index==0){
			break;
		}
		result++;
		for(j=0;j<top[index];j++){
			count[something[index][j]]--;
		}
		count[index]=0;
		int flag=0;
		for(j=0;j<510;j++){
			if(count[j]>0){
				flag=1;
				break;
			}
		}
		if(flag==0){
			break;
		}
	}
	printf("%d",result);
}

yohan5050 7년 전 4

그리디로 어떻게 하신건지 설명을 안해주셨고,

코드도 제 코드가 아니라 이해하기가 어려워서

뭐가 문제인지는 모르겠지만, 일단 반례 하나 알려 드릴게요.

10
1 6
2 8
3 2
4 9
5 5
6 10
7 4
8 1
9 7
10 3

정답으로는 6이 나와야하는데, 7이 나오네요.

dlftls38 7년 전 3

죄송합니다 더 설명을 드렸어야했는데 그러지 않았네요

각 전기줄에 겹친 다른 전기줄의 개수가 큰것부터 지워나가는 식인 그리디로 짠거였습니다

요한님 덕분에 어느정도 해결했네요 감사합니다..

백트래킹을 하면 배열을 다시 원상태로 돌려놔야한다는걸 지금 알았습니다 그래서 짰지만

시간초과가 나서 이 부분만 해결하면 될거같네요 감사합니다

#include <stdio.h>
int answer=10000;
int n;
int real[100]={0};
int p=0;
void re(int index,int result,int* count,int (*something)[100],int* top){
	int j,back_countindex,max=0;
	if(index>0){
		result++;
		for(j=0;j<top[index];j++){
			count[something[index][j]]--;
		}
		back_countindex=count[index];
		count[index]=0;
	}
	for(j=0;j<n;j++){
		if(max<count[real[j]]){
			max=count[real[j]];
		}
	}
	if(max==0){
		if(answer>result){
			answer=result;	
		}
		for(j=0;j<top[index];j++){
			count[something[index][j]]++;
		}
		count[index]=back_countindex;
	}
	else{
		for(j=0;j<n;j++){
			if(count[real[j]]==max){
				re(real[j],result,count,something,top);
			}
		}
		if(index>0){
			for(j=0;j<top[index];j++){
				count[something[index][j]]++;
			}
			count[index]=back_countindex;
		}
	}
}
int main(){
	int i,j;
	scanf("%d",&n);
	int a[510]={0};
	for(i=0;i<n;i++){
		int q,w;
		scanf("%d%d",&q,&w);
		a[q]=w;
		real[p]=q;
		p++;
	}
	int count[510]={0};
	int something[510][100]={0};
	int top[510]={0};
	for(i=2;i<510;i++){
		for(j=1;j<i;j++){
			if(a[i]<a[j] && a[i]!=0){
				count[i]++;
				count[j]++;
				something[i][top[i]]=j;
				top[i]++;
				something[j][top[j]]=i;
				top[j]++;
			}
		}
	}
	re(0,0,count,something,top);
	printf("%d",answer);
}

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

문제

문제

출처

ICPC

2565 전기줄 문제 반례 부탁드립니다!!!!!

dlftls38 7년 전 1

yohan5050 7년 전 4

dlftls38 7년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말