처음 description을 읽었을 때는 쉬운 구현문제라 생각하고 접근했는데, 8번 WA세례를 맞았네요ㅠㅠ 몇 번씩 제 가정들을 검토하고 검토해도 답이 안나와서.. 질문하게 되었습니다. ㅠㅠ
제 해법은 다음과 같습니다.
(가정) 각 메시지에 해당하는 답은 $C_i$ 또는 $0$이다.
왜? 답이 $C_i$보다 클 순 없다는 건 당연하다.
답이 $C_i$보다 작으려면 특정 사람에 대한 정보가 주어져야하는데
이 정보는 이후 메시지에 등장하는 $P_j$로만 얻어진다
그런데 이후에 $P_j$가 있다면, $P_j$는 이전 메시지를 모두 읽은 사람이다.
즉 특정된 사람이 있다면 $C_i$에 포함되지 않는다.
결국 $C_i$보다 답이 작아지는 경우는 없다.
즉, 답은 $C_i$ 혹은 추측이 불가능할 때 $0$이 된다.
(해법)
1) $T_i$를 기준으로 소트한다.
2) 시간 역순으로 순회하면서 1~N을 추가해둔 set을 유지한다.
이 set은 메시지를 읽지 않았다고 확정할 수 있는 사람들의 집합이다.
2-1) $P_i$를 set에서 제거한다.
2-2) $C_i$가 set의 크기와 같다면, 해당 메시지의 답은 $C_i$이다
2-3) 이외의 경우 답은 $0$이다.
3) 각 메시지에 해당하는 답을 출력한다.
처음엔 답안도 $T_i$에 소트된 순서대로 출력해서 WA를 받았는데
이 오류를 고치고 나서도 WA가 나오자 시무룩해졌습니다
...
헉 ㅋㅋ출제자의 답변이 올라오다니 영광이에요! 현재 메시지의 문제를 해결할 때, 이전 메시지에 대해서는 얻을 게 없다고 당연하게 여겨버렸는데-_-;; 이전메시지를 안읽은 사람에게 얻을 게 있었군요! 좀 더 신중하게 고민했어야 했습니다ㅠ_ㅠ 답변 감사드립니다, 덕분에 해결했습니다
restart
2회 전국 대학생 프로그래밍 연합 대회 문제를 하나 남기고ㅠㅠ
[[problem:TALKJAIL]]을 풀고 있는데요..
처음 description을 읽었을 때는 쉬운 구현문제라 생각하고 접근했는데, 8번 WA세례를 맞았네요ㅠㅠ 몇 번씩 제 가정들을 검토하고 검토해도 답이 안나와서.. 질문하게 되었습니다. ㅠㅠ
제 해법은 다음과 같습니다.
(가정) 각 메시지에 해당하는 답은 $C_i$ 또는 $0$이다.
왜? 답이 $C_i$보다 클 순 없다는 건 당연하다.
답이 $C_i$보다 작으려면 특정 사람에 대한 정보가 주어져야하는데
이 정보는 이후 메시지에 등장하는 $P_j$로만 얻어진다
그런데 이후에 $P_j$가 있다면, $P_j$는 이전 메시지를 모두 읽은 사람이다.
즉 특정된 사람이 있다면 $C_i$에 포함되지 않는다.
결국 $C_i$보다 답이 작아지는 경우는 없다.
즉, 답은 $C_i$ 혹은 추측이 불가능할 때 $0$이 된다.
(해법)
1) $T_i$를 기준으로 소트한다.
2) 시간 역순으로 순회하면서 1~N을 추가해둔 set을 유지한다.
이 set은 메시지를 읽지 않았다고 확정할 수 있는 사람들의 집합이다.
2-1) $P_i$를 set에서 제거한다.
2-2) $C_i$가 set의 크기와 같다면, 해당 메시지의 답은 $C_i$이다
2-3) 이외의 경우 답은 $0$이다.
3) 각 메시지에 해당하는 답을 출력한다.
처음엔 답안도 $T_i$에 소트된 순서대로 출력해서 WA를 받았는데
이 오류를 고치고 나서도 WA가 나오자 시무룩해졌습니다
...
무엇이 문제일까요ㅠㅠ?
11년 전