최적의 전략을 사용했을 때 최대 횟수가 나오는 케이스(worst case)는 다음과 같습니다.
말씀하신 대로, 1 2 3 4의 카드가 2장씩 존재하며, 이를 각각 11 12 21 22 31 32 41 42라고 하겠습니다.
시행 1. 11 21
시행 2. 31 12
시행 3. 11 12
시행 4. 41 22
시행 5. 21 22
시행 6. 32 31
시행 7. 42 41
다음 방법으로 7회가 나오게 됩니다.
14557번 - Memory
최적의 전략을 사용했을 때 최대 횟수가 나오는 케이스(worst case)는 다음과 같습니다.
말씀하신 대로, 1 2 3 4의 카드가 2장씩 존재하며, 이를 각각 11 12 21 22 31 32 41 42라고 하겠습니다.
시행 1. 11 21
시행 2. 31 12
시행 3. 11 12
시행 4. 41 22
시행 5. 21 22
시행 6. 32 31
시행 7. 42 41
다음 방법으로 7회가 나오게 됩니다.
앗...!! ㅎㅎ 그렇네용 생각해보니 새로운 카드를 밝히는 초반 뽑기에서 하나는 새로운 종류의 카드를 뽑고, 나머지 하나는 이미 나온 종류의 또 다른 카드를 뽑아서 모든 종류의 카드를 뽑는 횟수를 지연시킬 수가 있군용..!!
친절하게 알려주셔서 감사합니당
안녕하세요, 말씀하신 주장에 대한 반례를 제시해 보아도 될까요? 저는 카드가 4쌍인 상황을 이야기해 보겠습니다.
질문자님이 말씀하신 최악의 상황의 경우, $8$장의 카드 중 $1$ ~ $4$장의 카드의 종류가 모두 다른 상황이었습니다. 이 경우 $2$회의 시행착오를 통해 네 종류의 카드의 위치를 모두 확보하고, 그 다음 이어지는 $4$회의 시도에서는 아직 펼쳐보지 않은 카드들 중 아무거나 하나를 고른 후, 펼쳐본 카드들 중 그 종류에 대응하는 카드를 고르면 항상 정확하게 맞출 수 있으므로 해당 시나리오에서는 최악 $2 + 4 = 6$회의 시도를 해야 맞출 수 있는 것은 맞는 것 같습니다.
하지만 이것보다 더 최악인 상황이 있을 것 같습니다. 사실, $4$장의 카드를 펼쳐 모두 다른 종류의 카드임을 확보한 상황은 나름 유리한 상황일 수도 있어 보입니다.
카드들은 위와 같이 배치되어 있습니다. 최선을 다해 이 게임을 클리어해 보겠습니다. 최악의 상황을 상정했으므로 운은 최악인 상황입니다.
따라서, 이 상황에서는 시도 횟수가 $7$회가 되었습니다. 플레이어가 일부러 바보같은 선택을 한 것이 아닌, 정말로 정보가 부족해 최악의 선택을 한 상황이 되었습니다.
카드가 $5$쌍인 상황도 비슷한 예시를 적용해 보실 수 있을 것 같습니다. 만약 잘못된 점이 있다면 알려주세요!
와...!! 너무 친절하게 알려주셔서 감사해용 ㅠㅠ 제가 가장 '운이 없는 경우'를 충분히 고민하지 못했던 것 같습니다...!!
댓글을 작성하려면 로그인해야 합니다.
sisuforbrd 1년 전
안녕하세요,
문제에서 최적의 전략으로 문제를 풀 때 최대 행동 횟수를 구하는 방식에 대해 한 가지 의문점이 있어 의견 남깁니다.
예를 들어, 카드가 4쌍(총 8장) 있고, 카드 종류를 각각 1, 2, 3, 4라고 가정해 보겠습니다.
이 시점에서 모든 카드의 위치와 종류를 파악할 수 있으므로, 이후에는 어떤 카드를 뒤집더라도 이미 확인된 짝을 맞출 수 있습니다.
즉, 남은 4쌍의 카드를 각각 제거하는 데 추가 4회의 행동이 필요하므로, 총 6회의 행동으로 게임을 마칠 수 있습니다.
따라서 최대 행동 횟수는
p+⌈p2⌉
로 계산되어야 하며, 이 경우 p = 4이므로 4+⌈4/2⌉=4+2=6회가 되어야 합니다.
문제에서 만약 다른 방식으로 계산되었다면, 위 반례(카드 종류가 1,2,3,4인 경우)를 참고하여 수정이 필요하다고 생각합니다.
추가로, 카드가 5쌍(총 10장) 있고, 카드 종류를 각각 1,2,3,4,5라고 가정한다면
마찬가지로 이 시점에서 모든 카드의 위치와 종류를 파악할 수 있으므로 이후에 어떤 카드를 뒤집더라도 이미 확인된 짝을 맞출 수 있습니다.
따라서 이같은 경우에는 5+⌈5/2⌉=5+3=8회의 행동으로 게임을 마칠 수 있습니다.
확인 부탁드립니다.