시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 390 | 190 | 164 | 50.932% |
$N$ 개의 숫자 $0$ 과 $M$ 개의 숫자 $1$ 로 이루어진 길이의 $N+M$ 의 두 문자열 S 와 T 가 있다. 이 문자열을 가지고 두 곰곰이 친구가 서로 재미있게 놀다가 갑자기 한 곰곰이가 선을 넘어버렸다.
“선 넘지마”
라는 선언과 함께 문자열 S 와 T 가 선을 사이에 두고 분리되어 버렸다. 곰곰이는 이제 노는 것을 그만두고 문자열을 정리하기로 했다. 하지만 선을 넘을 수 없기 때문에 S 문자열 앞에 앉은 곰곰이는 S 문자열만, T 문자열 앞에 앉은 곰곰이는 T 문자열만 수정할 수 있다.
곰곰이는 문자열에서 임의의 인접한 두 문자의 위치를 바꿀 수 있다. 문자의 위치를 바꾸는 연산을 $X$ 번 수행하면 $X^2$ 만큼의 비용이 든다.
두 곰곰이는 각각 S 문자열에서 $X$ 번, T 문자열에서 $Y$ 번의 연산을 수행하여, S 와 T 가 같은 문자열이 되도록 만들고 싶다. 이 때, 두 곰곰이가 사용한 비용의 합의 최솟값, 즉 $X^2 + Y^2$ 값의 최솟값을 구해보자.
첫째 줄에는 음이 아닌 정수 $N$, $M$ 이 공백을 사이에 두고 주어진다. ($1 \le N + M \le 100\,000$)
이어 두 번째 줄과 세 번째 줄에 각각 문자열 S 와 T 가 주어진다.
문자열 S 와 T 의 길이는 $N+M$ 이며, $N$ 개의 숫자 $0$ 과 $M$ 개의 숫자 $1$ 로 이루어져 있다.
가능한 $X^2 + Y^2$ 의 최소값을 출력한다.
4 3 1100100 0100011
25
0101010 으로 만들면 최소가 된다.
3 0 000 000
0
2 2 1100 0011
8
1001, 0110 둘 다 가능한 모습이다. 1010 으로 만드는 경우, S 는 1번, T 는 3번의 연산을 수행해서 총 1+9=10 의 비용이 소모된다.
Contest > BOJ User Contest > 곰곰컵 > 제2회 곰곰컵 H번