jeongdongha   2년 전

21874번 모자 게임 질문있습니다.


제가 맨 처음 생각했던 코드는 전체 합을 구한 후 자신의 앞에 있는 모자 번호와 이미 불린 모자 번호를 빼면 답이 나온다고 생각했습니다.

다른 정답 코드들을 봤을 때

    1. %64

    2. bit 연산

을 사용해서 문제를 해결한 것을 봤는데 아래와 같이 짜면 안되는 이유를 알고 싶습니다.

Green55   2년 전

게임이 시작되면 맨 뒷 사람부터 순서대로 0 이상 63 이하의 정수 중 하나를 말한다.

jeongdongha   2년 전

답변 감사합니다.

하나 궁금한게 있는데 

(전체 합) - (앞에 있는 모자 합) - (이전에 부른 값 합) 은 항상 0 이상 63이하가 아닌가요??

Green55   2년 전

맨 뒷사람이 부르는 전체 합이 63을 넘을 수 있습니다

jeongdongha   2년 전

답변 정말 감사합니다!

제가 이해를 잘 못해서 다시 질문 드립니다.

위에 코드에서 n-1번 유저가 64 이상인 값이 나와 답이 아니란 것은 이해했습니다.

만약 아래 코드처럼 num=n-1로 주어졌을 때 전역변수 int sum에 저장하면 0<=F[i]<64 이니까

(sum) - (앞에 있는 모자 합) - (이전에 부른 값 합) 값이 0~63으로 보장되는 게 아닌가요??

실례가 안된다면 반례 하나 요청 드립니다... 

Green55   2년 전

https://www.acmicpc.net/board/...

를 참고해보세요

댓글을 작성하려면 로그인해야 합니다.