algospot.com :: 질문과 답변: ACM ICPC 2007 World Final Problem G. Network 질문입니다.

ACM ICPC 2007 World Final Problem G. Network 질문입니다.

Taeyoon_Lee

정확히 기억은 안 나지만, 한 메시지를 받기 시작했으면 무조건 그 메시지를 다 받을 때까지, 다른 메시지를 받으면 안 되는 걸로 기억해요. 해석의 모호함 때문에 많은 팀들이 낚인 것 같더라구요.

16년 전 link
leedohyun

그 의미는 1번 메시지를 받기 시작했다면 1번 메시지를 다 받을 때까지는, 다른 건 모두 버퍼에 저장해야 한다는 의미인가요??

16년 전 link
leedohyun

결국은 메시지 처리 순서에 대한 모든 조합에서 가장 작은 것을 선택해야 한다는 거죠??

16년 전 link
leedohyun

역시나 모든 조합을 구해서 가장 작은 값을 선택하는 게 맞군요. Accepted 했습니다^^
46 1.348 492 leedohyun C++ 2008-01-31 17:38:03 244966 (H1)

16년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

leedohyun: 오랜만에 ACM 문제를 풀어 보고 있습니다^^
근데 제목에 있는 문제가 잘 안 풀리네요-.-;
접근은 Greedy로 했는데요.
저지 사이트 (http://acmicpc-live-archive.uva.es/nuevoportal/) 에서 돌려보니 제가 미쳐 발견하지 못한 것이 있는지 WA 뜹니다.
메시지는 순서에 상관 없는 것이고, 패킷만 순서대로 통과하면 되는 것인데...
구현한 알고리즘은 간단히 소개하면요.
1. 패킷의 시작 바이트가 1인지 살핀다.
2. (1-YES) 바로 처리하고 버퍼에 이어지는 패킷이 있는지 확인하여 있을 때까지 처리한다.
3. (1-NO) 바로 앞 부분 패킷이 이미 처리가 되었는지 살핀다.
4. (3-YES) 2번 처럼 한다.
5. (3-NO) 버퍼에 저장한다.
맞는 풀이인가요??

[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

16년 전