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

문제 링크

---

1. 아이디어

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

---

2. 복잡도

접근	시간	공간
풀이	$O(1)$	$O(1)$

(GCD를 유클리드 호제법으로 구하지만 제수가 상수 6이라, 첫 나눗셈 뒤 두 인자가 모두 6 이하로 줄어 n 크기와 무관하게 상수 번의 스텝에 끝난다)

---

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.gcd를 표준으로 제공한다.

---