글 읽기 - 1005번ㅠㅠ

acm3352 9년 전 0

건물 번호와는 관계없이 하도록 바꿔봤는데, 여전히 안되네요 흑

맨 처음 건물 번호를 찾아서 그 건물부터 다음 빌드오더를 큐에 넣어가며 누적하도록 했는데, 이번엔 뭐가 문제일까요ㅠ

#include <cstdio>
#include <queue>
int cost[1000+1];
int m[1000+1][1000+1]={0};
int time[1000+1];
int check[1000+1]={0};
std::queue<int> Q;

void init(int n);
void getMinTime(int n,int numOfB,bool init);
int main()
{
	int numTestCases,num,numOfOrder;
	int i,j,n1,n2,endNum,temp,initNum;

	scanf("%d",&numTestCases);
	for(i=0; i<numTestCases; i++)
	{
		scanf("%d %d",&num,&numOfOrder);
		for(j=1; j<=num; j++)
			scanf("%d",&cost[j]);
        init(num);
		for(j=1; j<=numOfOrder; j++)
		{
			scanf("%d %d",&n1,&n2);
			m[n1][n2]=1;
			check[n2]=1;
		}
		scanf("%d",&endNum);
		for(j=1;j<=num;j++)
		{
			if(check[j]==0)
				getMinTime(j,num,true);
		}

		while(!Q.empty())
		{
			temp=Q.front();
			getMinTime(temp,num,false);
			Q.pop();
		}

		printf("%d\n",time[endNum]);
        
	}
}

void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            m[i][j]=0;
        time[i]=0;
		check[i]=0;
    }
}

void getMinTime(int n,int numOfB,bool init)
{
	int i,max=0;

	if(init == true)
		time[n]=cost[n];
	else
	{
		if(time[n]!=0)		// 중복방지
			return;
		for(i=1;i<=numOfB;i++)
		{
			if(m[i][n]==1 && n!=i)
			{	
				if( max < time[i] )
					max=time[i];
			}
		}
		time[n]=cost[n]+max;
	}
	
	
	for(i=1;i<=numOfB;i++)
	{
		if(m[n][i]==1 && n!=i)
			Q.push(i);		// 큐에 넣는다
	}
	return;
}

pichulia 9년 전 0

알고리즘은 맞습니다. 문제에 조건이 하나만 더 붙었었더라면 말이죠

현재 코드를 보면 X번 건물을 짓고나서 Y번 건물을 지을 수 있다는 조건에서

X < Y라는 조건을 암암리(?)에 생각하신듯 합니다.

안타깝게도 문제에는 저런 조건이 없습니다...

즉 2번건물을 짓고나서야 1번 건물을 지을 수 있는 상황도 데이터로 들어온다는 점이죠...

현재 코드에서 조금만 고친다고 해결되는 문제가 아닌거같네요.....

고생 좀 하실듯 합니다...ㅠㅠ

acm3352 9년 전 0

그것만은 아니길 바랬는데.. 역시군요 아무튼 감사해요~~

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

문제

문제

출처

ICPC

1005번ㅠㅠ

acm3352 9년 전 0

pichulia 9년 전 0

acm3352 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말