글 읽기 - 토렌트 문제 답은 맞았지만 이해가 안되는 부분이 있습니다.

ejrvheowkd 3년 전 0

글을 읽어주셔서 감사합니다.

제가 궁금한 부분은 조각을 가진 사람이 a초에서 b초 사이에 접속해있다고 할 때 이분 매칭 시작을 다운 받기 시작하는 시간으로 잡으면

답이 틀리고 다운을 받고 난 후의 시간으로 잡으면 답이 맞습니다.

다른 점을 찾아도 보이지 않아서 이 글을 씁니다.

뭐가 다른건가요???

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>

using namespace std;

int N, M;
int b[11010], visit[11010];
vector<vector<int>>adj;
bool dfs(int n)
{
	if (visit[n])return 0;
	visit[n] = 1;
	for (int i = 0; i < adj[n].size(); i++)
	{
		int v = adj[n][i];
		if (!b[v] || dfs(b[v]))
		{
			b[v] = n;
			return 1;
		}
	}
	return 0;
}
int bmatch()
{
	int ret = 0;
	for (int i = 0; i <=100; i++)
	{
		memset(visit, 0, sizeof(visit));
		if(dfs(i))ret++;
		if (ret == N)//조각을 원하는 만큼 다 받았으면 시작한 시점으로부터 1초후니깐 i+1반환
			return  i + 1; //만약 시작을 다운받은 후 시점으로 잡으면(즉 a+1) return i;로 해주시면 됩니다.
	}
	return -1; 
}
int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		memset(b, 0, sizeof(b));
		adj.clear();
		adj.resize(11100);
		cin >> N >> M; //N : 조각 수  M : 사람수
		for (int i = 0; i < M; i++)
		{
			int a, b,num;
			cin >> a >> b>>num;  //a: 접속하는 시간0 , b:나가는 시간 ,num: 가지고 있는 조각수
			vector<int> list;
			for (int k = 0; k < num; k++) //가지고 있는 조각수만큼 정보를 받아 list에 저장
			{
				int tmp = 0;
				cin >> tmp; 
				list.push_back(tmp);
			}
			/*
			밑에 부분이 궁금합니다.이부분을 a+1초 즉 다운 받은 후의 시간으로 잡고 풀면
			맞습니다.하지만 a초 다운 받기 시작하는 시간으로 하면 답이 틀리는데
			혹시 제 머리 돌을 꺠주실 분 있을까요??
            a+1초로 시작하면 for (int j = a+1; j <= b; j++)이렇게 잡으시면 됩니다.
			*/
			for (int j = a; j < b; j++) //a~b까지 접속하는 시간
			{
				for (int k = 0; k < num; k++)
				{	
					adj[j].push_back(list[k]);//adj 연결
				}
			}
		}
		/*int key = bmatch();
		if (key == 100 || key == -1)
			cout << -1 << endl;
		else
		cout << key << endl;*/
		cout << bmatch() << endl;
	}

	return 0;
}

crypt9 3년 전 0

5초에 진입했다가 5초에 나가면 (1초 미만으로 접속할 경우) 다운로드를 못받겠네요.

hbg1345 3년 전 0

시작시간과 파일을 이분 매칭하게 되면 어떤 노드가 0초의 시간과 연결될 수 있어서 그런 것 같습니다.

19 번째 줄을 보면 dfs 함수 내에서 v번 파일이 매칭이 되었는지 확인할 때 b[v]가 0 인지 아닌지를 보시는데,

b[v]는 0이 될 수도 있어서 b를 -1로 초기화 해주셔야 될 것 같습니다.

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

문제

문제

출처

ICPC

토렌트 문제 답은 맞았지만 이해가 안되는 부분이 있습니다.

ejrvheowkd 3년 전 0

crypt9 3년 전 0

hbg1345 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말