처음 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회 전국 대학생 프로그래밍 연합 대회 문제를 하나 남기고ㅠㅠ
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가 나오자 시무룩해졌습니다
...
무엇이 문제일까요ㅠㅠ?
9년 전