pjkov0824   3년 전

알고리즘 설명

가장 큰 K가 나올 때는 A와 B의 개수가 비슷하게 존재할 때(짝수의 경우는 N/2 씩, 홀수의 경우는 N/2 와  N - N/2)

A와 B가 비슷하게 존재한 상황 ex) 8 13

AAAABBBB -> 현재 짝의 개수는 4*4  = 16개

이때 A 하나를 B 끝으로 옮기면

AAABBBBA -> 짝의 개수는 3*4 = 12개

즉, A 하나를 옮길 때마다 B의 개수를 빼줌.


우리가 알고자 하는 것은 K

그렇다면 위에서 알아본 예시와 같이 Max_val - num_B * x = K + y 인 상황이 존재.

나눗셈 모양으로 정리하면 (Max_val - K) - num*x = y.

즉 x는 몫, y는 나머지.

x가 뜻하는 것은 넘어간 A의 개수

y가 뜻하는 것은 하나의 A가 건너간 B의 개수


예외 처리하고 구현하면 아래


제가 뭔가 놓친 것이 있을까요??

댓글을 작성하려면 로그인해야 합니다.