순서가 다르면 답도 달라지나요? 혹시 어떤 경우에 답이 달라질 수 있나요?
1043번 - 거짓말
순서가 다르면 답도 달라지나요? 혹시 어떤 경우에 답이 달라질 수 있나요?
이 문제는 파티가 입력 시간순서로 개최된다고 생각하고 풀 하면 "진실 전파" 가 일어나게 되는 파티의 이전 파티들의 참가자들에게는 진실이 전파되지 않게되서 답이 바뀔것 같긴 합니다.
예를 들면 문제의 예제 입력 4를 보면
4 5 1 1 1 1 1 2 1 3 1 4 2 4 1
마지막 다섯 번째 파티에서 진실을 알고 있는 1번이 4번에게 진실을 전파하게 되어, 네 번째 파티에서도 과장을 하지 못하게 되어 답이 3이 됩니다. 저도 처음에는 시간 순서라고 생각해서 답을 4라고 착각해 한참 헤맸습니다. 입력 순서가 시간 순서가 아니라고 명시해주면 더 좋을것 같습니다
우선 예제 입력 4의 정답은 $2$입니다. 순서가 있다고 가정할 경우 어떻게 문제에서 예상하는 실제 답과 다른 답이 나올 수 있는지 더 자세히 알고 싶습니다.
숫자를 착각했네요 죄송합니다.
예제 입력 4
4 5 1 1 1 1 1 2 1 3 1 4 2 4 1
문제 풀이
진실을 아는 사람: 1
진실을 아는 사람과 함께 파티에 참가한 사람들이 진실을 알게됨
-> 진실을 알수 있는 사람: 1, 4
1 번째 파티 (1): 거짓말 불가능
2 번째 파티 (2): 거짓말 가능
3 번째 파티 (3): 거짓말 가능
4 번째 파티 (4): 거짓말 불가능
5 번째 파티 (4 1) : 거짓말 불가능
-> 정답: 2
이건데
파티가 시간 순서가 있다고 가정할 경우 (파티의 순서는 입력 순으로 가정)
진실을 아는 사람: 1
1 번째 파티 (1): 거짓말 불가능
2 번째 파티 (2): 거짓말 가능
3 번째 파티 (3): 거짓말 가능
4 번째 파티 (4): 거짓말 가능
5 번째 파티 (4 1) : 거짓말 불가능, 4도 진실을 알게됨
-> 정답: 3
이런식으로 정답이 달라집니다. 따라서 문제 조건에
"어떠한 시간 순서로 파티가 진행되더라도 거짓말쟁이라고 낙인 찍히지 않는 파티를 골라야 한다."
이런 문구가 있었으면 위와 같은 방식으로 헷갈릴 일이 없을것 같은데, 어떻게 생각하시나요??
답변이 늦어 죄송합니다.
본 문제에는 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 라는 중요한 조건이 있습니다. 이 조건은 순서를 가리지 않으며 어떤 사람이 서로 다른 두 파티에서 서로 다른 이야기(한쪽은 진실 / 한쪽은 거짓)를 듣는 순간 지민이가 거짓말쟁이로 알려지게 됩니다.
파티가 시간 순서가 있다고 가정할 경우에도 $4$번째 파티에서 거짓말을 하고 $5$번째 파티에서 진실을 말하게 되는 경우 $4$번 사람이 진실된 이야기와 과장된 이야기를 모두 듣는 상황이 펼쳐지게 됩니다. 그래서 $4$번 파티에서만 거짓말을 하는 경우가 불가능하며 두 파티 모두에서 진실을 이야기해야만 거짓말쟁이가 되는 상황을 피할 수 있을 것입니다.
중요한 조건 자체가 순서와 별개로 작용하는 것이기에 문제에서는 순서대로 파티가 진행됨을 굳이 언급하지 않아도 성립하는 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
rjsdh15963 1년 전 3
파티는 동시에 개최된다는 사실을 명시해주면 좋을 거 같습니다. 파티에 순서가 있는지 없는지 정확하게 명시되어있지 않습니다.
파티를 여는 순서가 있다면 답은 달라질 수 있습니다.