BOJ 3144 자석
문제 내용
개의 자석이 가로로 놓여 있습니다. 각각의 자석 또한 가로로 놓여 있으며, 어떤 자석의 N극과 다른 자석의 S극이 서로 마주보고 있으면 두 자석은 서로 붙게 됩니다.
자석을 뒤집는 시행을 하여 정확히 개의 연속된 자석이 붙은 것을 얻고자 할 때, 시행의 최소 횟수를 구하세요. 여러 개의 붙어 있는 자석은 한 번에 뒤집을 수 있습니다.
문제 풀이
스포일러
개짜리 자석 덩어리의 경계는 반드시 입력에 있는 N/N 또는 S/S 경계들 중 하나여야 합니다. 또한, 그 경계를 유지하면서 그 내부의 모든 자석을 하나로 연결하려면, 그 영역 내의 맨 왼쪽과 맨 오른쪽 자석은 같은 방향을 보고 있어야 합니다. 단, 첫 번째 자석의 왼쪽이나 마지막 자석의 오른쪽을 경계로 갖는 경우는 상관 없습니다.
입력에서 그 영역 내의 자석 덩어리의 개수를 라고 하면, 그 내부에 경계는 개 존재합니다. 한 번의 뒤집기 시행으로 내부 경계를 최대 2개 제거할 수 있으므로, 시행의 최소 횟수는 입니다.
이제 길이 짜리 슬라이딩 윈도우를 하면서 덩어리의 개수를 세고, 경계 조건을 충족할 때 답을 업데이트하면 됩니다.