1. 문제

Codeforces 2181H. Honey Cake

0.webp

  • time limit per test: 3 seconds

  • memory limit per test: 1024 megabytes

w * h * d 크기의 케이크를 n명이 나눠먹을 수 있도록 w, h, d축과 평행하게 케이크를 잘라 나누어야 한다. 모든 조각은 가로, 세로, 길이가 동일해야하며, 자른 조각의 가로, 세로, 길이는 정수여야 한다.

  • 입력: 케이크의 가로, 세로, 높이 w, h, d가 한 줄에 공백으로 나누어 들어온다. 다음 줄에는 케이크를 나눠먹어야 하는 인원 수 n이 주어진다.

  • 출력: 모두가 같은 크기의 케이크를 나눠먹기 위해서 w, h, d축으로 각각 몇 번 잘라야 하는지 공백을 기준으로 나누어 출력한다.

    만약 같은 크기의 정수들로 케이크를 나눌 수 없다면 -1을 출력한다. 자르는 횟수는 0회(한 축을 통째로 1개로 취급)일 수도 있다는 점에 유의한다.

2. 풀이

케이크를 자르는 횟수는 각 축 방향으로 자른 후의 개수를 따른다. 우선 각 축 방향으로 자른 후 개수를 축 별로 w_c, h_c, d_c라 하자.

각 축의 길이는 w_c, h_c, d_c의 배수여야 하며, w_c * h_c * d_c는 n과 같아야 한다.

$$ w_c | w, h_c | h, d_c | d $$

$$ n = w_c * h_c * d_c $$

이를 인수의 관점에서 생각해보자. 각 축 방향의 개수들은 각 축의 길이와 n을 동시에 나누는 약수, 즉 공약수다. n은 각 축 방향의 개수들의 곱과 같기 때문에, 이는 곧 n의 소인수를 각 축의 길이의 소인수 안에서 반드시 찾을 수 있어야 한다는 뜻이다.

사실 이 필요조건을 생각하는 것까지는 어렵지 않은데, 이것이 충분조건에 해당하는 지를 떠올리는 것은 조금 어색할 수 있다. 우리가 생각한 방법이 충분조건에 해당하는 지를 확인하려면 그 방법이 불가능한 경우의 수를 떠올려보면 좋다.

예를 들어, w축으로 자를 개수를 정하는 과정에서, n의 인수 중 매우 큰 값을 이미 계산해버렸다고 가정해보자. 예를 들어 케이크를 10조각으로 나누기만 하면 되는데 이미 w축으로 10번을 잘라버린 것이다. 이후 h축과 d축을 자르는 과정에 문제가 생길까?

문제에서 이미 0번 자르는 것이 가능하다는 점을 미리 일깨워주었다. 즉, h축과 d축은 자르지 않고 그냥 그대로 두어도 10 * 1 * 1 = 10이 되어 10조각을 만들 수 있게 된다. 인수의 곱셈 횟수 자체는 * 1로 그 횟수를 무한히 늘릴 수 있기 때문에 앞선 축에서 먼저 많이 잘라버려서 뒤의 축에서 자르지 못하게 되는 것을 걱정할 필요가 없다. 이를 인수의 관점으로 풀어보면 앞선 축에서 n에 필요한 소인수를 얼마나 많이 소모하던 간에, 뒤의 축에는 아무 관련 없는, 독립적인 문제가 된다. 문제가 되는 것은 모든 축에서 자를 만큼 잘랐는데도 n의 소인수를 다 소모하지 못한 경우 뿐이다.

결국 핵심은 앞 축에서 얼마나 자르든, 뒷 축에서 얼마나 자르든 관계 없이 n의 소인수를 w, h, d를 통해 모두 소모 시킬 수만 있으면 아무 문제가 없다는 것이다.

자, 그러면 이제 답을 뽑아내보자. 재밌게도 이 문제는 특정 입력에 대해 여러 개의 답이 나올 수 있다. 실제로 정해진 답과 달라도 가능한 값이기만 하면 정답으로 처리된다. 우리는 가능한 답 중에 하나를 최대한 빨리 찾아내기만 하면 된다.

각 축에서 n에서 소모할 수 있는 소인수를 최대한 많이 소모시키는 빠른 방법 중 GCD(최대공약수)를 사용하는 법이 있다. 예를 들어 w와 n의 최대공약수 만큼 w를 자르면 n에서 w가 소모시킬 수 있는 최대한 많은 소인수를 제거시킨 것이라고 할 수 있다.

GCD를 통해 문제를 푸는 법을 ‘각 축에서 n에서 소모할 수 있는 최대한의 소인수를 모두 소모시키며 검사한다’로 바꾸면, 각 축은 n에서 최대한의 소인수를 제거하기 위해 최선을 다한 것이기 때문에 모든 축을 자른 뒤에도 n을 만들지 못했다면 애초에 n의 소인수 중 w, h, d를 나눌 수 있는 소인수가 없다는 뜻이므로, 반드시 실패하는 경우임을 보장할 수 있다.

GCD를 활용하여 각 축에서 최대한의 소인수를 뽑아내는 방식으로 풀기 때문에 이를 GCD Greedy 문제로 볼 수 있다.

3. 코드

#include <iostream>
#include <numeric>

#define FAST_IO std::ios::sync_with_stdio(false); std::cin.tie(nullptr)

using namespace std;
using lli = long long int;

int main(void) {
    FAST_IO;

    lli w = 0, h = 0, d = 0;
    lli n = 0;
    cin >> w >> h >> d >> n;

    lli w_c = gcd(n, w);
    n /= w_c;

    lli h_c = gcd(h, n);
    n /= h_c;

    lli d_c = gcd(d, n);
    n /= d_c;

    if (n == 1) {
        cout << w_c - 1 << ' ' << h_c - 1 << ' ' << d_c - 1 << endl;
    } else {
        cout << -1;
    }

    return 0;
}

C++17부터 <numeric>에서 std::gcd 함수를 제공하기 때문에 이를 통해 빠르게 코드를 작성할 수 있다.