문제 - 탑코더 바이너리 플립


A장의 0과 B장의 1이 주어지는 게임이 있습니다. 여러분의 목표는 모든 것을 1로 바꾸는 것입니다.


턴마다 정확히 K장의 숫자를 선택하고 숫자를 반전합니다 (0은 1로 바귀고, 1은 0으로 바꿉니다).


현재 값에 상관없으며 이미 반전한 숫자도 원하는 대로 턴마다 선택할 수 있습니다. 


게임에서 이기기 위한 최소 턴 수를 리턴하세요. 게임에서 이기는 것이 불가능 하다면 -1을 리턴하세요.


/////////////////////////////////////////




책에 나온 코드 설명


i번째 턴에서 모든 카드를 1로 만들 수 있다고 가정하면 카드를 뒤집는 횟수는 다음과 같습니다


i x K번


또한 원래 0이었던 것이 A장 있으므로 A장은 반드시 뒤집어야 합니다.


나머지를 뒤집는 횟수를 rest라고 하면 rest는 다음과 같이 구할 수 있습니다.


rest= i x K - A장


이 나머지 rest가 같은 카드를 2번 뒤집는 조작을 몇 번 반복할지가 됩니다.


조작이 가능한 횟수는 다음과 같습니다.


원래 카드가 0일 때는 (i-1)/2 번


원래 카드가 1일 때는 i/2 번


이유는 간단합니다. 0의 카드는 반드시 최초에 한 번 뒤집어야 합니다.


반면 1의 카드는 처음부터 1이므로 처음부터 이유 없이 뒤집을 수 있는 횟수를 use라고 하면 다음과 같이 표현할 수 있습니다.


use = ((i/2) x B + ((i-1)/2) x A ) x 2


지금까지 계산한 rest와 use를 이용하면 다음과 같은 조건을 얻을 수 있습니다.


1. A 장 이상 뒤집을 수 있어야 합니다 rest >= 0 


2. 뒤집는 수의 홀수 짝수가 일치해야 합니다. rest %2 = 0   


3. 이유없이 뒤집을 수 있는 조작이 충분해야 합니다.  rest <= use    


이러한 3가지 조건이 충족되면 가정에 모순되지 않게 i번째 턴에서 모든 카드를 1로 만드는 것이 가능합니다.





/////////////////


1번 조건 해석


rest >= 0 -> i*K - A >= 0 -> i* K >= A


당연히 i번째 턴에서 뒤집는 횟수가 A장보다 많아야함. (0을 1로 만드는 최소 조건)



2번 조건 해석


rest 는 카드 초기 상태에서 0을 1로 뒤집을 때 빼고 나머지를 뒤집는 횟수임.


rest = i * K - A


그러면 카드를 뒤집다가 i번째 턴에서 모든 카드가 1이라고 가정해보면


rest는 짝수여야만 가능함.


왜냐하면 초기 0이었던 카드는 무조건 뒤집어야함. 1로 만들어야 하니깐.


그러면 나머지 카드 뒤집는 애들은 현상 유지를 해야함. 1 -> 0 -> 1 


그러려면 당연히 짝수여야됨. 홀수면 아무리 숫자가 커도 1 -> 0 -> 1 -> 0 -> 1 .... -> 0


결국엔 0으로 끝나니깐 답이 안됨. 


고로 rest % 2 == 0



3번 조건 해석


i번째 턴에선 A를 1로 바꾸는 뒤집기 제외하고 


I*K - A 만큼 뒤집기 소비를 해야함.


use 를 뒤집일 수 있는 모든 경우의 수의 총집합이라고 생각하면 됨.


0인 카드가 있고 5번째 턴에서 1을 만들어야 할 때는 최대 4번밖에 못 뒤집음. -> (i-1)/2 * 2


1인 카드가 있고 5번째 턴에서 1을 만들어야 할 때는 최대 5번 뒤집기 가능 -> i/2 * 2


0인 카드는 A장 있고 1인 카드는 B장 있으니


(i-1)/2 * 2 * A + i/2 * 2 * B -> ((i-1)/2 * A + i/2 * B) * 2


따라서 use는 저식이 나오는 거임.


이런 모든 경우의 수 총집합에서 rest만큼을 소비해야함 무조건!


그래서 당연히 rest <= use 여야함.




그렇다면 위에 3가지 조건이 충족될 때 왜 i번째 턴의 카드가 모두다 1이냐?


이게 좀 이해 안 갈 수 있음.


일단 1은 당연히 이해갈 거고 (기반을 깔아주는 조건)


use에서 좋은 조건만 뽑아다가 rest를 소비시켰을 때인데 i번째 턴에서 답이 나온다는 건데,


일단 use가 rest 보다 작으면 좋은 조건을 뽑을 것도 없음, (3번도 역시 기반을 깔아주는 조건)


1,3이 충족됐을 때 rest가 짝수다?


그러면 A였던 애들을 제외하고 나머지 1이였던 애들이 1-> 0 -> 1 -> 0 ..... ->1


다 1로 돌아왔다는 뜻임.




고로 이 3가지 조건만 충족하면 i번째 턴에서 답이 나옴 ㅇㅋ?