안녕하세요,
재재입니다.
BOJ 26075 곰곰아 선 넘지마 문제 풀이입니다.
BOJ 26075 곰곰아 선 넘지마
(1) 문제 설명
분류 : greedy
출처 : https://www.acmicpc.net/problem/26075
1이 N개, 0이 M개 사용된 문자 S와 T가 주어집니다.
S에서 X개를 바꾸고, T에서 Y개를 바꿨을 때,
$$ X^2 + Y^2 $$ 의 최소값을 구해주면 됩니다.
(2) 풀이 도출
이 문제의 핵심은 1이나 0을 중 한가지만 선택한 다음,
위치를 배정 하는 것에 있습니다.
그리고 여기서 위치를 배정 할 때는,
둘의 중간 위치에서 만나는 게 가장 효과적인데요.
한쪽의 끝 방향에서 시작하면 항상 만들 수 있습니다.
다만,
중간 위치가 딱 떨어지지 않는 경우 X 와 Y 중 적당히 작은 것을 한번 더 옮기면 됩니다.
(greedy)
(3) 정답 코드
BOJ 26075 곰곰아 선 넘지마