[백준]2163.초콜릿자르기 (미제)

풀지 못했다. 순환식을 찾지 못했기 때문이다. 내가 자른 방식이 최소라고 어떻게 보장할 수 있을까?

1.역으로 생각하여 1x1타일부터 시작하여 최소를 찾는다. 

2. n*m이 잘릴 수 있는 모든 경우를 구한다. 이때, 메모제이션을 이용하면 1x1부터 시작한 결과를 얻을 수 있다.

3. 수학적으로 생각해본다. n과 m이 짝수일 경우 자를 수 있는 수는 아래 왼쪽이 (n-1,m-1)이 된다. 그리고 아래나 오른쪽을 반으로만 자른다고 가정하고, 아래를 자른다면 다를 수 있는 수는 (log_{2}(n-1) , 2*(m-1))이 된다. (아래는 잘렸으므로 반으로 줄어들고, 오른쪽은 아래가 반으로 잘렸기에 복제되어 오른쪽으로 자를 횟수는 2배가 된다.) 두 수가 모두 0이될 때까지 반복한다. 만약 한쪽이 0이 된다면 0이된쪽은 자르지말고 다른 한쪽만 자른다.

 

1,2,3 모두 동시에 적용할 수 있는 사항이긴한데... 시도하진 않았다. 돌아가는 느낌이 강해서.

다른 사람들이 푼 것을 참고하니 증명없이 가정하에 진행한 것만이 보였다. 좀 더 생각해보자