글 읽기 - 6퍼센트에서 틀렸다고 뜹니다.

skwyun 3년 전 0

위상정렬로 풀었습니다. 각종 예제들 다 잘 나오는데 왜 자꾸 틀리는지 모르겠네요. ~~싸지방 연등시간 2시간 내내 이것만 했는데~~....반례 또는 틀린점 또는 개선사항 알려주시면 감사하겠습니다 ㅠㅠ

#include <cstdio>
#include <queue>
#include <functional>
#include <vector>

using namespace std;

vector <int> v[30];
priority_queue <int, vector<int>, greater<int> > q;
priority_queue <int, vector<int>, less<int> > minq;

int main()
{
	int n, max_ind[30], min_ind[30], ans;
	int minn[30], maxn[30];
	char ch[30];
	
	scanf("%d", &n);
	for(int i=0;i<n;i++){
		scanf("%s", &ch[i]);
		if(ch[i] == '<'){
			max_ind[i]++;
			min_ind[i]++;
			v[i+1].push_back(i);
		}
		else if(ch[i] == '>'){
			max_ind[i+1]++;
			min_ind[i+1]++;
			v[i].push_back(i+1);
		}
	}
	for(int i=0;i<=n;i++){
		if(max_ind[i]==0){
			q.push(i);
			minq.push(i);
		}
	}
	ans = 9;
	while(!q.empty()){
		int e = q.top();
		q.pop();
		maxn[e] = ans--;
		for(int i=0;i<v[e].size();i++){
			int x = v[e][i];
			if(--max_ind[x] == 0) q.push(x);
		}
	}
	ans = n;
	while(!minq.empty()){
		int e = minq.top();
		minq.pop();
		minn[e] = ans--;
		for(int i=0;i<v[e].size();i++){
			int x = v[e][i];
			if(--min_ind[x] == 0) minq.push(x);
		}
	}
	
	
	for(int i=0;i<=n;i++)
		printf("%d", maxn[i]);
	printf("\n");
	for(int i=0;i<=n;i++)
		printf("%d", minn[i]);
	
	return 0;
}

skwyun 3년 전 0

자문자답입니다. 위상정렬 시 들어오는 간선의 갯수를 더해주는 배열을 초기화 하지 않아 벌어진 일이었네요. 구름ide로 코딩하면서 답이 잘 나오길래 생각하지도 못한 문제였습니다. 재밌네요 ps....하...초기화도 안했는데 테스트 어떻게 나온거여 그동안....

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

문제

문제

출처

ICPC

6퍼센트에서 틀렸다고 뜹니다.

skwyun 3년 전 0

skwyun 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말