해설가장 많이 등장하는 크기의 등장 횟수를 FFF라고 하자. 한 묶음에는 서로 다른 크기의 떡 두 개가 필요하다. 어떤 크기가 F>N/2F>N/2F>N/2번 등장한다면 그 크기의 떡은 다른 크기의 떡과만 묶을 수 있으므로 최대 N−FN-FN−F개를 만들 수 있다. 반대로 F≤N/2F\leq N/2F≤N/2라면 가장 많은 크기도 나머지 떡들과 충분히 짝지을 수 있어 ⌊N/2⌋\lfloor N/2\rfloor⌊N/2⌋개를 만들 수 있다. 따라서 정답은 min(⌊N/2⌋,N−F)\min(\lfloor N/2\rfloor,N-F)min(⌊N/2⌋,N−F)이다. 빈도만 세면 되므로 해시 맵을 사용하면 기대 시간 복잡도는 O(N)O(N)O(N)이다. Solution written by GPT5.6
