2개의 댓글이 있습니다.
-
-
kriii -
어떤 사람의 성이 남성인 경우 1 여성인 경우 0이라고 합시다.
그러면 두 사람 a,b가 있을때 a*b = 1이면 악수 0이면 포옹이 되는겁니다.
이제 하이퍼 시니어의 각 멤버의 성을 a0 ~ aN-1까지라고 하고, 이를 다항식으로 나타냅시다.
a0 x^0 + a1 x^1 + ... + aN-1 x^N-1그리고 팬들도 똑같이 성을 b0 ~ bM-1이라고 하고 다항식으로 나타냅시다. 여기서 주의할점은 계수를 위와는 반대로 해줘야 합니다
bM-1 x^0 + bM-2 x^1 + ... + b0 x^M-1이제 이 두 다항식을 곱합니다.
그래서 계수가 0인 항의 개수를 세주면 모두 포옹하는 일의 횟수가 됩니다. 왜그런지는 직접 한번 해보면 됩니다...저같은 경우 FFT를 이용해서 O(NlgN)만에 풀었습니다.
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
장홍준
문제링크 : FANMEETING
문제를 직접 풀어보신 후, 솔루션을 공유해주셨으면 합니다.
제가 푼 방법은 아래와 같습니다.
하이퍼시니어의 멤버 수를 N, 팬들의 수를 M이라 하겠습니다.
문제에서 중요한 요소는 하이퍼시니어의 남성 멤버들이 남성 팬과는 포옹하기가 민망하다는 사실입니다. 이를 이용하면 i번째(1<=i<=M-N+1) 팬부터 i+N-1번째 팬까지 중에서 하이퍼시니어의 남자 멤버에 대응되는 위치의 팬이 남자가 아닐 경우, 모든 하이퍼시니어의 멤버들이 팬들과 포옹하게 됩니다.
하이퍼시니어의 맴버들과 팬들을 단순히 비교하기엔 그 수가 많기 때문에 일정 수(저의 경우 60명)의 멤버들을 묶어서 한 집단으로 생각하여 접근을 하였습니다. 남녀를 이진수로 정의하면 한 집단은 0부터 2^59까지의 값을 가지게 되는 것입니다. 이렇게 자료를 재구성할 경우, 하이퍼시니어 멤버 수와 팬들의 수가 1/60로 감소하며, AND(&) 연산을 통해서 해당 자리의 사람들이 포옹을 할 지 판별할 수 있습니다.
좀 더 구체적으로 말하면 하이퍼시니어 멤버(A[i]) 중 남성을 1, 여성을 0이라하고 팬(B[i]) 중에서 남성인 팬을 0, 여성인 팬을 1로 할 경우, (A[i] & B[i])==A[i]이면 그 그룹 내의 모든 사람들은 포옹을 하게 되는 것입니다.
팬들의 경우 1번째부터 Min(60, M)번째까지 시작 지점을 바꾸어가며 그룹핑을 해야하고, 각 집단의 마지막 그룹을 서로 비교할 시에는 사람 수가 일치하는지의 추가적인 고려사항들도 몇 가지 있지만 큰 틀은 위와 같습니다.
수행시간이 빠르신 분들의 소스코드를 보니 Naive한 솔루션에 critical한 경우 한 가지만을 예외처리 해주셨길래 질문드립니다. 다르게 푸신 분들은 간략하게라도 풀이를 공유해주시면 감사하겠습니다.
10년 전