BinaryFlips

문제

A장의 0과 B장의 1이 주어지는 게임이 있다

목표는 모든 것을 1로 바꾸는 것이다

턴 마다 정확히 K 장의 카드를 선택하고, 숫자를 반전합니다

( 현재 값 상관없이 반전 가능, 바꾼 카드를 다시 반전하는것도 가능 )

게임에서 이기기 위한 최소 턴수를 리턴하고, 불가능하면 -1 을 리턴한다

A : 0 ~ 100,000
B : 0 ~ 100,000
K : 0 ~ 100,000

예시 입력

3, 0, 3
4, 0, 3
4, 1, 3
3, 2, 5
100000, 100000, 578
0, 0, 1
4, 44, 50

예시 출력

1
4
2
-1
174
0
-1

생각의 변화

A4 B0 K3

1000 또는 0001 폼을 만든다
0001 도 가능

1111 이 되려면
0001 인 형태를 만든다

뒤집을 카드를 선택했을때
0 : A가 줄어들때 B가 늘어난다
1 : B가 줄어들때 A가 늘어난다

a -= i
b += i

b -= K-i
a += K-i

dfs 는 탐색제한 조건이 애매

1111 부터 탐색하고 0000 을 찾으러 간다
bfs 를 사용

직전 선택을 기억해두고, 이번 선택이 직전 선택을 원복 시키는 경우는 제외

데이터 구조가 필요할까
현재 a, 현재 b, 직전 선택, 턴 을 기억하며 탐색

pseudo code

struct data
{
	int currentA;
    int currentB;
    int prev_moveA;
    int prev_moveB;
    
    int turn;
};

minimalMoves(A, B, K)
    if (A == 0)
        return 0

    if (A == K  &&  B == 0)
        return 1
        
    if (A+B <= K)
        return -1

    
    queue<struct data> q
    
    turn = 0
    q.push({0, A+B, K, -K, turn})    // all 1

    while (!q.empty())
        struct data d = q.front()
        q.pop()
        
        a = d.currentA
        b = d.currentB
        prev_move_a = d.prev_moveA
        prev_move_b = d.prev_moveB
        turn = d.turn
        
        if (a == A  &&  b == B)
            return turn
            
        for (i = 0; i < K; i++)
            move_a = 0
            move_b = 0
            
            if (i <= a  &&  K-i <= b)
                move_a -= i
                move_b += i
                move_b -= K-i
                move_a += K-i
                
                if (move_a == prev_move_b  &&  move_b == prev_move_a)
                
                else
                    q.push({a + move_a, b + move_b, move_a, move_b, turn + 1})

    return turn

100000, 100000, 578 시간초과

100000 을 서서히 줄여가는데, 탐색범위가 지나치게 넓어지는 문제가 있다

생각의 변화

탐색 범위를 좁히기 위해 다음 생각모델을 사용한다.

1) 0의 갯수를 알면 1의 갯수를 알수 있다 -> 0의 갯수만 저장

2) bfs 시 최초로 발견된 결과가 '최소이동횟수' 이다

따라서 dist[i] 에 0 의 갯수가 i 인 때에 이동횟수를 적으면 자연스럽게

bfs 탐색을 하면서 이동횟수가 증가된다

그리고 0을 뒤집는 갯수 x, 탐색중일때의 0을 u 라고 할때

naive 하게 접근하면 0 <= x <= K 로 생각할수 있지만

실제로는 범위 제한이 있다

max_x
x 는 K 보다 작아야 하고
x 는 u 보다 작아야 한다

그리고 1을 뒤집는 갯수 K-x 를 생각하면

min_x
K-x 는 A+B-u 보다 작아야 한다

따라서 식으로 나타내면

max_x = min(K, u)

min_x = max(0, K-(A+B-u))

x 는 조건을 모두 만족해야 하므로
max_x 를 정할땐 min 숫자를 사용했고
min_x 를 정할땐 max 를 사용하였다

이 범위 내에서 다음 x 값인 v 를 구해본다

v 는 u 에서 시작한다
0 을 x개 뒤집으면 -x
1 을 K-x개 뒤집으면 (K-x)

따라서 식으로 나타내면

v = u + K - 2*x

pseudo code

minimalmoves(A, B, K)
    if (A == 0)
        return 0
        
    vector<int> dist[A+B+1, -1]
    queue<int> q
    
    dist[A] = 0
    q.push(A)
    
    while (!q.empty())
        u = q.front()
        q.pop()
        
        if (u == 0)
            return dist[0]
        
        max_x = min(K, u)
        min_x = max(0, K-(A+B-u))

        for (x=min_x  x<=max_x  x++)
            v = u + K - 2*x

            if (v >= 0 && v <= A+B && dist[v] == -1)
                dist[v] = dist[u] + 1
                q.push(v)
            
    return -1