[Java] 백준 31443 - 준영이

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

---

풀이

크기가 3인 조각을 최대만 많이 만들면 된다.

예외적으로 크기가 4인 조각은 2×2로 쪼개는 게 더 이득이다.

---

증명

(식이 길어져 미분 과정은 생략)


아무튼 초코바를 일정한 크기의 조각으로 나누고 초코바가 해당 크기로 딱 알맞게 나눠진다는 가정하에는 조각의 크기가 e = 2.718281828 일 때 기쁨의 수치가 최대가 된다. 이 값은 반올림하면 3이니까 대강 3으로 나눠보자.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	public static final int MOD = 1000000007;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		long answer = 1;
		int size = N * M;

		while (size > 4) {
			answer *= 3;
			answer %= MOD;
			size -= 3;
		}
		answer *= size;
		answer %= MOD;

		System.out.println(answer);
		br.close();
	}
}

---

테스트 케이스

case #1:
5 6
59049

case #2:
5 7
354294

case #3:
5 8
2125764

case #4:
7 8
774840978

case #5:
1 1
1

---

후기

조그만 생각해보면 초코바를 최대한 잘게 자르면 되겠다는 감이 온다.

(∵ 어떤 수 xª를 크게 만들기 위해서는 a를 크게 만드는 게 이득이니까)

근데 테스트케이스를 만들다 보니 예상외로 2보다는 3이 더 이득이라 당황했던 문제..

그리디는 매번 혼란스럽다..