자유 게시판
프로그래밍 문제 하나
2021.05.13 00:25
프로그래밍 문제
~~~~~~~~~~~~~~~~~~~~~~~~~~~
0과 1로만 이루어져 있으며, 0의 개수와 1의 개수가 동일한 문자열 S가 주어진다. 당신은 S에 다음과 같은 작업을 여러 번 수행할 수 있다:
S의 길이 2k인 연속한 부분문자열이 앞 k개 문자가 모두 동일하고, 또한 뒤 k개 문자가 서로 동일하며, 0과 1을 모두 포함할 때, 그 부분문자열을 제거할 수 있다.
예를 들어, S = “0111000011”인 경우, S의 2번째 문자부터 7번째 문자까지인 “111000”을 제거하는 것이 가능하다. 이 작업 후에는 제거된 부분의 앞부분과 뒷부분이 연결되어 S = “0011”이 된다. 그러면 이제 한 번의 작업을 통해 “0011”을 제거할 수 있으므로 초기 S = “0111000011”는 두 번의 작업을 통해 빈 문자열로 만들 수 있다.
여러분의 목표는 최소 횟수의 작업을 통해 S를 빈 문자열로 만드는 것이다. 최소 횟수의 작업으로 S를 빈 문자열로 만드는 과정을 구하여라.
~~~~~~~~~~~~~~~~~~~~~~~~~~~
문제가 원래 그런건지, ton3d님이 줄여 쓰느라 잘못 쓴 것인지는 알 수 없지만,
'S의 길이 2k인 연속한 부분문자열이 앞 k개 문자가 모두 동일하고, 또한 뒤 k개 문자가 서로 동일하며, ' 부분과 뒤에 예시로 든
S = “0111000011”가 서로 오류입니다.
'k개 문자가 모두 동일해야 한다'면 2k인 s문자는 00001111, 111111000000 이런식이어야 하지 않나요?
그래서 문제가 맞고 예시가 틀렸다면, 어떤 문자열이 와도 이 문제는 1번만 제거가 이루어 집니다.
설명이 잘못된듯 합니다.
오류찾기가 생활화된 프로그래머는 이런 문제를 안냅니다.