제2회 곰곰컵 풀이

A - 치킨댄스를 추는 곰곰이를 본 임스 2 풀이
B - 붙임성 좋은 총총이 풀이
C - 곰곰이와 학식 풀이
D - 오락실에 간 총총이 풀이
E - 곰곰이와 시소 풀이
F - 외로운 곰곰이는 친구가 있어요 풀이
G - 곰곰이와 테트리스 풀이
H - 곰곰아 선 넘지마 풀이
I - 곰곰이의 식단 관리 2 풀이
J - 서커스 나이트 풀이

BOJ 26075 - 곰곰아 선 넘지마 링크
(2022.12.01 기준 G4)

문제

 N개의 숫자 0과 M개의 숫자 1로 이루어진 N+M 길이의 두 문자열 S와 T가 있다.
인접한 두 문자의 위치를 바꿀 수 있는 연산이 있으며 각 문자열에서 X번 수행했다면 총 X^2의 비용이 든다.
각각 S 문자열에서 X번, T 문자열에서 Y번의 연산을 수행하여 S와 T가 같은 문자열이 됐을 때, X^2 + Y^2 최솟값 출력

알고리즘

X와 Y가 제곱이 되어 합을 이루기 때문에 X와 Y가 합이 최소로 또한 X와 Y의 차이가 최소로 줄여야 X^2 + Y^2의 최솟값을 구할 수 있다.
다시 말하면 S에서의 연산과 T에서의 연산이 골고루 나뉘어야 한다는 것이고 또한 합이 최소가 되어야 하기 때문에 만나게 하기 위한 두 대상을 두 위치의 중간에서 만나게 해야 한다.
결국 그리디

풀이

그림을 보면 바로 이해가 갈 것이다.

찾고자 하는 대상을 먼저 정하자. 당연히 적은 갯수의 숫자를 찾는 것이 나을 것이다.
위의 예시에선 1을 찾아야 한다.
각 문자열에서 1의 위치를 전부 찾자.
S에선 [0, 1, 4], T에선 [1, 5, 6]이 나온다.

그렇다면 나온 순서대로 위치를 살펴보자.
처음엔 0과 1이다. 그렇다면 S[0]을 오른쪽으로 옮기던가 T[1]을 왼쪽으로 옮기면 된다. 일단 S[0]을 옮기자.
다음은 1, 5. S[1]을 오른쪽으로 2칸, T[5]를 왼쪽으로 2칸 옮기면 된다.
마지막으로 4, 6. S[4]를 오른쪽으로 1칸, T[6]을 왼쪽으로 1칸 옮기면 된다.

그럼 총 연산은 X = 4, Y = 3
X^2 + Y^2 = 25

숫자가 커질수록 제곱은 더욱 더 커지기 때문에 X와 Y를 최소한으로 만든다고 생각하면 쉽다.

코드

import sys; input = sys.stdin.readline

N, M = map(int, input().split())
S = input().strip()
T = input().strip()

# 더 적은 갯수의 숫자를 찾자.
find = '0' if N < M else '1'
pos = [[] for _ in range(2)]
for i in range(N + M):
    if S[i] == find:
        pos[0].append(i)
    if T[i] == find:
        pos[1].append(i)

# 순서대로 두 위치의 중간으로 연산을 각 해주자.
# 만약 차이가 홀수이면,
# 현재 연산 횟수가 작은 쪽에 1을 더하자.
X = Y = 0
for i in range(min(N, M)):
    dif = abs(pos[0][i] - pos[1][i])
    cal = dif // 2 # 차이의 반이 연산 횟수가 된다.
    X += cal
    Y += cal
    if dif % 2:
        if X < Y:
            X += 1
        else:
            Y += 1
print(X * X + Y * Y)