글 읽기 - 양 구출 작전 잘 모르겠습니다.

kwb6675 4년 전 0

혹시 반례 있나요 ? 재귀함수는 여러번 봤는데 어디서 틀린지 잘 모르겠네요 ,,

// 모바일공학과 김원빈
// 양 구출 작전

#include <stdio.h>

int sheep[123457];
int check[123457];
int count;
int N;

struct Tree
{
	int w, s, parent;
}node[123457];

void Escape(int n);

int main()
{
	char t;
	int n, a, p;

	scanf("%d", &N);

	for (n = 2; n <= N; n++)
	{
		scanf(" %c %d %d", &t, &a, &p);

		if (t == 'W')
		{
			node[n].w = a;
			node[n].parent = p;
		}

		if (t == 'S')
		{
			node[n].s = a;
			node[n].parent = p;
			sheep[++count] = n;
		}
	}

	for (n = 1; n <= count; n++)
	{
		if (check[sheep[n]] == 0)
		{
			Escape(sheep[n]);
		}
	}

	printf("%d\n", node[1].s);
}

void Escape(int n)
{
	int s, w;

	check[n] = 1;
	
	if (node[n].s == 0) { return 0; }
	if (n == 1) { return 0; }

	s = node[node[n].parent].s;
	w = node[node[n].parent].w;

	if (w <= node[n].s)
	{
		node[n].s -= w;
		s += node[n].s;
		w = 0;
	}

	else
	{
		w -= node[n].s;
		s = 0;
	}

	node[node[n].parent].s = s;
	node[node[n].parent].w = w;

	node[n].s = 0;
	node[n].w = 0;

	Escape(node[n].parent);
}

djm03178 4년 전 0

답이 int 범위를 넘어갈 수 있습니다.

kwb6675 4년 전 0

감사합니다 수정했습니다 ! 하지만 계속 시간초과가 나는데 혹시 가지치기를 어디서 더할수있는지 알수있나요? 로직을 바꿔야하나용 ?

// 모바일공학과 김원빈
// 양 구출 작전

#include <stdio.h>

int sheep[123457];
int check[123457];
int count;
int N;

struct Tree
{
	long long s, w;
	int parent;
}node[123457];

void Escape(int n);

int main()
{
	char t;
	int n, p;
	long long a;

	scanf("%d", &N);

	for (n = 2; n <= N; n++)
	{
		scanf(" %c %lld %d", &t, &a, &p);

		if (t == 'W')
		{
			node[n].w = a;
			node[n].parent = p;
		}

		else if (t == 'S')
		{
			node[n].s = a;
			node[n].parent = p;
			sheep[++count] = n;
		}
	}

	for (n = 1; n <= count; n++)
	{
		if (check[sheep[n]] == 0)
		{
			Escape(sheep[n]);
		}
	}

	printf("%lld\n", node[1].s);
}

void Escape(int n)
{

	long long s, w;

	if (n == 1) { return 0; }
	check[n] = 1;

	if (node[n].w <= node[n].s)
	{
		node[n].s -= node[n].w;
		node[n].w  = 0;
		node[node[n].parent].s += node[n].s;
		node[n].s = 0;
		Escape(node[n].parent);
	}
	
	else
	{
		node[n].w -= node[n].s;
		node[n].s = 0;
		return 0;
	}
}

djm03178 4년 전 0

이렇게 하면 최악의 경우 O(n)개의 섬을 거쳐가는 경로를 O(n)번 수행하게 되기 때문에 O(n^2) 시간이 됩니다.

가지치기는 거의 대부분의 알고리즘에서 정해가 아닙니다. 로직을 바꿔야 합니다. 주어진 그래프가 트리라는 점을 이용해서, 한 섬에 대한 처리는 한 번만 할 수 있게 만들어 보세요.

kwb6675 4년 전 0

감사합니다 :) 위상정렬과 비슷하게 해결하였습니당 !

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

문제

문제

출처

ICPC

양 구출 작전 잘 모르겠습니다.

kwb6675 4년 전 0

djm03178 4년 전 0

kwb6675 4년 전 0

djm03178 4년 전 0

kwb6675 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말