BOJ 25456 궁금한 시프트
문제 내용
0과 1로만 이루어진 길이 의 두 문자열 와 가 주어집니다. 와 , 그리고 0 이상 미만인 두 정수 와 를 지문에 주어진 함수에 넣었을 때 얻을 수 있는 리턴 값 중에서 최댓값을 출력하세요.
문제 풀이
스포일러
먼저, 지문의 코드는 인 의 쌍에 대해 S[i] == '1' && T[j] == '1' ? 1 : 0의 합을 구하고 있습니다. 이는 S[i] * T[j]의 합을 구하는 것과 동치입니다.
그리고 모든 와 에 대해, 임의의 상수 를 골라 과 을 입력으로 넣어도 같은 결과를 얻을 수 있으므로, 으로 고정해도 됩니다.
이제 BOJ 1067 이동과 동일한 방법으로 를 뒤집은 후 FFT를 사용하여 원하는 개의 값을 모두 구하고, 그 중 최댓값을 골라 출력하면 됩니다.