[Programmers] #120815 - 피자 나눠 먹기 (2) [Java][C++][Python]

문제 링크

---

1. 아이디어

피자 한 판이 6조각으로 잘리고, n명이 조각을 하나도 남기지 않고 모두 같은 개수만큼 나눠 먹으려면 최소 몇 판을 시켜야 하는지 구하는 문제다. 전체 조각 수는 한 판당 6조각의 배수이면서 동시에 n명에게 고르게 나눠떨어져야 하므로, n과 6의 공배수 중 최솟값인 최소공배수여야 한다. 최소공배수는 $\text{lcm}(n, 6) = \dfrac{n \times 6}{\gcd(n, 6)}$로 구할 수 있고, 판수는 6조각 단위이므로 이를 6으로 나눈 $n / \gcd(n, 6)$가 된다. GCD는 유클리드 호제법으로 구한다.

---

2. 복잡도

접근	시간	공간
풀이	$O(\log(\min(N, 6)))$	$O(1)$

($N$ = n. 유클리드 호제법의 스텝 수는 두 값 중 작은 쪽의 크기에 비례하는데, 한쪽 값이 항상 6으로 고정돼 있어 실질적으로는 상수에 가깝다.)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int n) {
        return n / gcd(n, 6);
    }

    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

Java는 표준 라이브러리에 정수 GCD 함수가 없어 유클리드 호제법을 직접 구현했다.

#include <bits/stdc++.h>
using namespace std;

int solution(int n) {
    return n / gcd(n, 6);
}

C++17부터는 <numeric>(<bits/stdc++.h>에 포함됨)의 std::gcd를 바로 쓸 수 있다.

import math


def solution(n):
    return n // math.gcd(n, 6)

Python도 math 모듈의 math.gcd를 표준으로 제공한다.

---