12970번 - AB
알고리즘 설명
가장 큰 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의 개수
예외 처리하고 구현하면 아래
제가 뭔가 놓친 것이 있을까요??
댓글을 작성하려면 로그인해야 합니다.
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의 개수
예외 처리하고 구현하면 아래
제가 뭔가 놓친 것이 있을까요??