BOJ 15134 - Dividing Marbles

문제 태그 : https://www.acmicpc.net/problem/15134

※ 내가 관찰로 푼 문제들 중 하나이다. 따라서 갑자기 생각난 아이디어와 노가다, 말도 안되는 관찰들로 풀이가 이루어 질 예정이다.
※ 2018 NEERC가 끝난 후 LOTUS와 함께 풀었다. 

문제 소개

테스트 케이스 별로 a,b,c,d 숫자 4개가 주어진다. 총 구슬의 갯수 $n=2^a+2^b+2^c+2^d$이다. 이때 우리는 n개의 구슬인 1묶음을 1개의 구슬씩 n개의 그룹으로 나누어야 한다. 이때 한 번의 행동으로 다음과 같은 작업을 할 수 있다. 
 - (A,B,C) 그룹의 크기가 A인 모든 그룹을 각각 크기가 B인 그룹과 C인 그룹으로 나눈다. (이때 $A=B+C$)
이때 그룹의 최대 크기가 1이 될때까지 걸리는 행동의 최소 횟수와 그 방법을 출력하시오.

문제 풀이

풀이 1

일단 예제를 살펴보았다. 6->2->1, 15->5->1 이 눈에 띄었다. 가장 먼저 생각할 수 있는건, 같은 크기의 그룹을 만들수록 이득이라는 것이다. 그래서 처음에 하게 된 생각은 '무조건 내 약수중에 하나로 모였다가 거기서부터 출발 하는것은 어떨까?' 였다. 그래서 DP인 첫 풀이가 완성되었다. 
$DP[i]=($문제에서 $N=i$ 일때의 정답$)$ 이라고 하면  
$DP[i]=\underset{j|i}{min}(DP[j]+DP[i/j])$ 가 된다. 
내가 코드를 짜다가 이상해져서 LOTUS 한테 부탁하니까 LOTUS가 뚝딱 짜왔다. 당연히 결과는 틀렸습니다. 
- 만약 당신이 루비 풀이가 떠올랐다면 그건 루비가 아니거나 풀이가 아니다-

풀이 2

이번엔 문제의 입력 방식에 집중했다. 1의 풀이대로라면 그냥 $N<=2^{22}$를 줬어도 된다. 왜 4개의 비트를 주었을까?
그러다가 이런 생각을 했다. 최상위 비트를 계속 절반씩 쪼개면 아래 비트를 같이 쓸어나갈 수 있다는 것을 발견했다.
그러니까 a>b>c>d인 a,b,c,d가 주어지면 $N=2^a+2^b+2^c+2^d$인 N을 3번의 행동을 통해 비트별로 쪼갠 뒤에, a번의 행동을 추가로 사용해 $2^a->2^{a-1},2^{a-1}$ 방식으로 쪼개 나갈 수 있다는 것이었다. 
그래서 만들어진 두번째 풀이는 N을 비트로 쪼갠뒤 켜진 비트 수+최대 비트 값-1 이 답이었다.
이것도 결과는 틀렸습니다... - 만약 당신이 루비 풀이가 떠올랐다면 그건 루비가 아니거나 풀이가 아니다-

※ 앞으로 a>b>c>d 임을 가정하고 서술 하겠습니다. 
※ (a,b) = 그룹의 크기가 $2^a+2^b$임을 의미합니다. 
※ 차수는 가장 큰 비트를 의미합니다. 

반례 찾기

위 두 풀이를 비교하다가 27이 나왔다. 27=16+8+2+1 이라서 풀이 2에 따르면 7번이지만 사실 6번에 된다. 여기서 한가지 아이디어가 번뜩였다.

a,b,c,d 가 a-b=c-d 를 만족하면 a+2번에 가능한거 아닌가?
1. 처음에 (a,b),(c,d)로 쪼갠다.
2. (a,b)를 계속 절반으로 쪼개서 (a-1,b-1),(a-2,b-2)........(c-d)까지 만든다.
3. (c,d)를 한꺼번에 (c),(d)로 쪼갠다.
4. c를 다시 0까지 쪼갠다.

위 과정을 거치면 최대 차수가 내려가는 횟수는 a번이지만 한번에 두개의 묶음을 쪼갤 수 있어서 총 a+2번이 나온다. 

하지만 풀이 1일때는 6이었고, 둘 다 맞지 않는 반례를 찾기 위해서 1부터 쭉 다 해보았다.
두 번째 반례는 23이었다. 
(23 - 20,3)  (20 - 10,10) (10 - 5,5) (5 - 3,2) (3 - 2,1) (2 - 1,1)
23은 두가지 모두 7회가 나왔지만 실제로 6번만에 가능하다. 이 반례를 뚫어져라 분석한 결과 이 반례를 위의 반례처럼 일반화 시킬 수 있었다.

a-b=c-d+1일때도 a+2번에 가능하다. 

1. (a,b) 랑 (c,d)로 나눈다.
2. (a,b)를 (c+1,d)이 될때까지 절반으로 쪼갠다.
3. (c+1,d)=(c,d)+c 으로 쪼갠다.
4. (c+d)=(c),(d)로 쪼갠다.
5. c를 마저 0까지 내린다. 

위에서는 (a,b)와 (c,d)의 쪼개는 부분이 자연스럽게 겹쳤다면, 이번 경우는 3번 과정을 통해 최대 차수를 내리면서 쪼개는 것을 같이 할 수 있었다. 

나는 그래서 답이 a+2인 경우는 a-b=c-d와 a-b=c-d+1일때 밖에 안된다고 성급하게 단정지었다. 그럴 것 같았다.
비트가 4개가 아니라 3,2,1 인경우는 구간이 겹칠 수 없으니까 a+2,a+1,a 일것이라고 생각했다. 무조건 구간이 겹쳐야만 줄일 수 있을 것 같았고, 그냥 그럴 것 같은 감이 세게 왔다.

풀이 2.5

위의 풀이 2에다가 두 가지 반례를 껴넣었다. 과정 출력은 내가 설명했던 그 방법 그대로 갔다. 

또 틀렸다. 손으로 반례를 더 찾다가 (5,2,1,0) = (4,3,1)+(3,2,0) 을 깨달았다. 쪼개면서, 최대 차수를 내릴 수 있었다. 나중에 다시 겹칠 수도 있어 문제도 되지 않는다. 새벽 3시 반이었다. 죽는 줄 알았다. 희망이 없었다.
"일단 오늘은 졋잘싸로 마무리 할듯 ㄹㅇ 이래야 루비지"

풀이 3.5

?????????? 3.5=1+2.5다. 그렇다. 1번 풀이와 2.5번 풀이를 합쳤다. DP테이블의 횟수와 바로 계산해 줄 수 있는 횟수를 비교해서 더 작은 값을 따른다가 풀이였다. 너무 힘들어서 코드 두개 복붙하고 잘 쓰까서 그냥 이거 내보고 자야지 했는데, 맞았다. 

증명

왜 맞았는지 모르겠는데, 알고보니 맞을만했다. 

1. 켜진 비트가 3개 이하면 한 번에 두 개의 행동을 해서 이득을 볼 수 없다. 따라서 a+비트수-1 이다.
2. 맨처음에 켜진 4개의 비트를 나누는 방법에는 두 개의 숫자에 대한 켜진 비트가 (3 3),(3 2),(2 2)인 경우가 있는데, 3개 짜리 비트의 최소 횟수는 a+2이기 때문에 처음에 차수가 하나 줄어야 하며, 둘 중에 하나를 쪼개는 과정에서 나머지 하나가 무조건 다 쪼개져야 한다. 따라서 둘 중 나머지 하나가 다른 것의 배수여야 한다.
3. 따라서 남은 것은 (2 2)로 쪼갤때 뿐이고, 이 경우는 2개의 쪼개지는 곳이 완벽이 겹쳐져야 하는데 이런 경우가 발생하기 위해서는 a-b=c-d or a-b=c-d+1을 만족해야 한다.
4. 따라서 두 경우를 섞으면 예외 처리가 완벽하게 된다.