BOJ 32073 XOR 최대
문제 내용
0과 1로 이루어진 길이 의 문자열 가 주어집니다. 여기서 두 개의 부분문자열을 골라서, 이들이 이진수로 나타내는 값을 XOR한 결과가 최대가 되도록 하여 그 결과를 출력하세요.
모든 테스트 케이스에서 의 합
문제 풀이
스포일러
주어진 문자열에 1이 존재하지 않으면 부분 문자열을 어떻게 골라도 값이 0이 되므로 답은 0입니다.
결과의 길이를 최대화하려면 하나의 1을 고르고 그 뒤에 최대한 많은 개수의 문자를 고른 문자열이 적어도 하나 있어야 합니다. 이는 에서 맨 왼쪽의 0을 모두 제거한 것과 같습니다. 이를 으로 둡니다.
의 모든 글자가 1이면, 의 값을 0으로 만들 수 있으면 이 답이고 아니면 "1"이 가능한 가장 작은 값을 가지므로 이 답이 됩니다.
아니라면, 의 맨 왼쪽에 있는 1의 묶음의 길이를 , 그 바로 뒤에 있는 0의 묶음의 길이를 라고 합시다. 이제 목표는 맨 앞의 개의 1은 건드리지 않고 바로 뒤에 최대한 많은 1을 채우는 것입니다.
의 길이는 정확히 여야 하고, 0으로 시작하는 것은 도움이 되지 않으므로, 반드시 구간 내에 시작점이 존재하고, 의 시작 위치에 올 수 있는 연속한 1의 개수는 1개 이상 개 이하입니다.
이면 개를 모두 사용하여야 연속된 1의 개수를 최대화할 수 있습니다.
이면 정확히 개를 사용하는 것이 최적입니다. 그 이유는 개를 초과할 경우 선택된 1이 바로 뒤에 붙어있는 1과 XOR되어 0이 되어버리기 때문입니다.