글 읽기 - 좀더 효율적인 방법이..?

petil777 8년 전 0

제 방법대로 하면 같은 의미를 나타내는게 2번호출되어 실제 경우의 수보다 2배커지게 됩니다

처음에 cache로 메모를 할때 0으로 했더니 30%까지 가고 시간초과가 발생해서 고민해보니 이미 불가능해서 0가지로 확정된 경우를 cache가 기본적으로 0이다 보니까 구분이 안가서 불가능한 경우를 반복해서 세게 된다는 걸 알게됐습니다.

그래서 cache를 -1로 초기화하고 조사를 할 때 마다 0으로 세팅해서 한번 불가능 확정된 경우를 다시 보지 않게 하였더니 바로 틀렸습니다...(30%Accept된 코드와 여러개 예시를 만들어 넣어서 비교해봤는데 제가 넣어본 것은 모두 일치하더군요..)

따라서 제 알고리즘 논리에서 어느 부분이 잘못됐는지 알고 싶습니다.

참고로 dfs과정에서 혹시 수 범위를 벗어나지 않을까 하여 500개 발판이 있고 모두 서로 왔다갔다 할 수 있는 최악의 경우를 고려했을 때 unsigned long long으로 터지지 않아서 괜찮다고 판단했습니다.

그리고 이 방법이 잘못됐다면 보다 효율적으로 짤 수 있는 방법(점화식)힌트 좀 주세요 ㅠ.ㅠ

#include <cstdio>
#include <memory.h>

int n;
unsigned long long int cache[501][501];
struct info{
	int idx, spring, spec;
};
info step[501];
//A는 가는길 B는 오는길 저장
bool Acan(int a, int next)
{
	return step[next].idx - step[a].idx <= step[a].spring;
}
bool Bcan(int b, int next)
{
	return (step[next].idx - step[b].idx <= step[next].spring) && step[next].spec;
}

unsigned long long int dfs(int A, int B)
{
	if (A == n)
	{
		if (Bcan(B, n)) return 1;
		return 0;
	}
	if (B == n)
	{
		if (Acan(A, n)) return 1;
		return 0;
	}

	unsigned long long int& ret = cache[A][B];
	if (ret != -1) return ret;
	ret = 0;
	int next = (A + 1) > (B + 1) ? A + 1 : B + 1;

	//ite가 next+1이면 next는 선택하지 않고 가능 경우
	for (int ite = next; ite <= n; ite++)
	{
		if (!Acan(A, ite)) break;//A가 해당 ite와 멀어서 더이상 나아갈 수 없는 경우 그만 조사

		if (Acan(A, ite)) ret += dfs(ite, B);
		if (Bcan(B, ite)) ret += dfs(A, ite);
	}

	return ret;
}
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d%d%d", &step[i].idx, &step[i].spring, &step[i].spec);
	memset(cache, -1, sizeof(cache));
	printf("%d", (dfs(1, 1) / 2) % 1000);
}

baekjoon 8년 전 0

방법이 맞긴 한데, 조금 고치면 될 것 같네요.

참고로 문제에서 1000으로 나눈 나머지를 출력하라는 경우는, int나 long long 의 범위를 넘어갈 수 있기 때문입니다.

https://www.acmicpc.net/problem/10430

이 문제를 풀어보면, 어떻게 고쳐야하는지 알 수 있습니다. 그리고, 위의 문제만 고친다고 해서 정답이 되지는 않습니다.

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