글 읽기 - 안녕하세요^^ 부탁드립니다ㅜㅜ

dkwkekzz 7년 전 0

아래코드가 왜 정답이 아닌지 궁금합니다.

처음점과 마지막 점을 0과 c+1에 집어넣습니다. 그리고 카운트를 1씩 늘리면서 각 카운트당 몇가지 경우가 생기는지 탐색합니다. 이를 위하여 가능한 모든 시작점과 도착점을 매칭하며 정해진 시작점과 도착점에서 두 점을 제외한 오락실이 보일 경우 무시하며 경우의 수를 셉니다.

C[end][count] = count개의 오락실을 지나갈 시, end로 갈 수 있는 경우의 수

countPath()는 start와 end사이에 또 다른 오락실을 지나지 않으면서 start에서 end로 도달하는 경우의 수입니다.

정답인 코드와 어느정도 큰 값에 대해 실행 후 비교해본 결과는 같았습니다.

도와주십시오 ㅜㅜ

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <cmath>
using namespace std;
typedef long long int64;

const int64 INF = 987654321, MAX_N = 55, MOD = 1000007;
int64 n, m, c;
int64 O[MAX_N][2], P[MAX_N][MAX_N], C[MAX_N][MAX_N];

int64 countPath(int from, int to){
	int64 &ret = P[from][to];
	if (ret != -1) return ret;

	int64 temp[MAX_N][MAX_N];
	memset(temp, 0, sizeof(temp));
	for (int y = O[from][1]; y <= O[to][1]; y++){
		for (int x = O[from][0]; x <= O[to][0]; x++){
			if (y == O[from][1] && x == O[from][0]) temp[y][x] = 1;
			else temp[y][x] = (temp[y - 1][x] + temp[y][x - 1]) % MOD;
			for (int i = from + 1; i < to; i++){
				if (y == O[i][1] && x == O[i][0]){
					temp[y][x] = 0;
					break;
				}
			}
		}
	}
	return ret = temp[O[to][1]][O[to][0]];
}

void solve(){
	C[0][0] = 1;
	for (int count = 0; count <= c; count++){
		for (int start = count; start <= c; start++){
			for (int end = start + 1; end <= c + 1; end++){
				C[end][count + 1] += (C[start][count] * countPath(start, end)) % MOD;
				C[end][count + 1] %= MOD;
			}
		}
		printf("%lld ", C[c + 1][count + 1]);
	}
	printf("\n");
}

/*int findPath(int y, int x, int count){
	for (int i = count; i <= c; i++){
		if (y == O[i][1] && x == O[i][0]) count++;
	}

}*/

int main(){
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);

	memset(P, -1, sizeof(P));
	scanf("%lld%lld%lld", &n, &m, &c);
	for (int i = 1; i <= c; i++) scanf("%lld%lld", &O[i][0], &O[i][1]);
	O[0][0] = 1, O[0][1] = 1; O[c + 1][0] = n, O[c + 1][1] = m;
	solve();

	return 0;
}

dkwkekzz 7년 전 1

문제에 오락실의 입력이 내림차순으로 주어진다는 조건이 없는 것에 착오가 있었네요^^; 한참 해멨습니다~

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

문제

문제

출처

ICPC

안녕하세요^^ 부탁드립니다ㅜㅜ

dkwkekzz 7년 전 0

dkwkekzz 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말