[백준 31443번] 준영이 (C++)

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

초코바의 가로 세로 길이가 입력으로 주어지고 초코바를 쪼갰을때 나눠주는 조각의 넓이가 기쁨이고 준영이가 얻는 기쁨은 나눠준 기쁨의 총 곱이다.

 

이 문제는 백준1437번 수 분해와 완전히 똑같은 문제이다. 구체적인 증명이 어려운 문제인데 결론적으로는 1*3짜리를 가장 많이 만들면 된다. 어떤 자연수(원래 초코바의 넓이)를 분해한 수들(초코바 조각들의 넓이)의 곱(총 기쁨)은 3을 가장 많이 사용했을 때 가장 커진다. 

자연수가 아니라면 자연상수인 e(2.718xxx...)의 제곱들이 가장 큰 수를 만든다. 문제의 조건에서 초코바 조각들의 길이는 항상 정수여야한다고 했으므로 e와 가장 가까운 3으로 나누는 경우가 가장 곱들이 커지는 경우가 된다.

(사실 e하고 가깝다고 하기보다는 2보다 3에서 함수값이 더 크고 e에서 극댓값을 가진다.)

 

마지막으로 3*1을 최대한 많이 만들고 나머지가 1*1인 경우에는 3*1을 하나 지우고 2*2짜리를 넣어주는게 더 수가 커지므로 이 부분만 유의하면 된다.

 

#include <iostream>
#include <cmath>
#define ll long long
#define MOD 1000000007
using namespace std;

int main() {
    ll n, m, a, b, c, ans = 1;
    cin >> n >> m;
    a = n*m;
    if(n < 3 && m < 3) {
        cout << n*m;
        return 0;
    }
    b = a/3;
    c = a%3;
    if(c == 1) b--;
    while(b--){
        ans *= 3;
        ans %= MOD;
    }
    if(c==1) ans *= 4;
    if(c==2) ans *= 2;
    cout << ans%MOD;
}