백준 31443 준영이

문제

https://www.acmicpc.net/problem/31443

31443번: 준영이

 

풀이

어떤 수 a^b 를 크게 만들기 위해선 a가 작아지더라도 b를 크게 만드는게 이득이다. 즉 초콜릿 조각수는 많을수록 좋다.

1x1초콜릿 조각은 아무런 이득이 되지 않는다.

무조건 1x2조각으로 채우는 것은 이득이 아닐 수도 있다.

1x6에서 1x2조각으로 3개 나누는 것과 1x3조각으로 2개나누는 것을 비교하면 8 < 9이므로 1x3조각으로 나누는 것이 이득이다.

따라서 최대한 많은 1x3조각을 가져가는게 좋다.

하지만 1x4조각에서 1x1,1x3조각으로 나누는 것 보다 1x2조각 2개로 나누는 것이 이득이다. 3 < 4이기 때문이다.

따라서 풀이 전략을 이렇게 정할 수 있다.

1.최대한 많이 1x3조각으로 자른다.

2.그러다가 1x1조각이 나온다면, 1x3조각 하나와 1x1조각을 버리고 1x2조각 2개로 바꾼다.

3.1x2조각이나 2x1조각이 나온다면 어쩔 수 없으므로 그대로 가져간다.

 

약간 더 구체화 해보자.

현재 초콜릿 조각에 대해 가로가 x고 세로가 y이다.

1. x,y 모두 3미만이라면 그만둔다.

2. 가로를 기준으로 1x3조각을 만들고 세로는 y등분하는게  좋은지, 세로를 기준으로 1x3씩 자르고 가로는 x등분하는게 좋은 지 체크한다.

여기서 좋다는 것은 1x3조각을 최대한 많이 만드는 것이다.

3. 해당 판단을 기준으로 1x3조각을 만든다.

4. 남은 꼬다리에 대해 1-3을 반복한다. 꼬다리가 없다면 종료

5. 종료한 이후 1x1조각이 있으면 1x3조각을 하나 제외하고 1x2조각 2개를 만들어준다.