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

문제 링크

---

1. 아이디어

피자를 여섯 조각으로 잘라줄 경우 n명이 동일한 조각 수의 피자를 먹기 위해 필요한 피자의 최솟값을 구해야 한다. n이 100이하의 자연수이므로 피자의 수를 cnt라고 할 때 cnt를 1부터 증가시키며 $6 \times cnt \bmod n = 0$ 인 cnt가 나올 때까지 반복하면 된다.

$6 \times cnt$ 이 n의 배수가 되는 최소 cnt를 찾는다는 점에서 6과 n의 최소공배수인 $\text{lcm}(6, n)$ 을 구한 후 이를 6으로 나누면 이것이 cnt가 되는데 $\text{lcm}(6, n) = \dfrac{6 \times n}{\gcd(6, n)}$ 이므로 $\dfrac{n}{\gcd(6, n)}$ 를 구하는 것으로 빠르게 해결할 수도 있다.

---

2. 복잡도

1. 브루트 포스

시간복잡도	공간복잡도
$O(N)$	$O(1)$

N = 매개변수 n

2. 유클리드 호제법

시간복잡도	공간복잡도
$O(1)$	$O(1)$

---

3. 코드

1. 브루트 포스 [Java][C++]

class Solution {
    public int solution(int n) {
        int cnt = 1;
        while (true) {
            if (6 * cnt % n == 0) return cnt;
            cnt++;
        }
    }
}

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

int solution(int n) {
    int cnt = 1;
    while (true) {
        if (6 * cnt % n == 0) return cnt;
        cnt++;
    }
}

2. 유클리드 호제법 [Java][C++]

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

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

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

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

---