Post

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

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

문제 링크


1. 아이디어

피자를 남기지 않고 $n$명이 같은 수의 조각을 먹으려면 전체 조각 수가 $n$의 배수여야 한다. 판 수를 $k$라 하면 조각 수는 $6k$이므로, $6k$가 $n$의 배수가 되는 가장 작은 $k$를 찾는 문제다. $6k$는 6과 $n$의 공배수이고 그중 가장 작은 것이 최소공배수 $\text{lcm}(n, 6)$이므로 $k = \text{lcm}(n, 6) / 6$이다. 최소공배수는 $\text{lcm}(n, 6) = 6n / \gcd(n, 6)$이라 결국 $k = n / \gcd(n, 6)$이다.


2. 코드

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

1
2
3
4
5
6
7
8
9
10
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);
    }
}

gcd는 유클리드 호제법으로 직접 구현했다.

1
2
3
4
5
6
#include <bits/stdc++.h>
using namespace std;

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

std::gcd로 최대공약수를 직접 구현하지 않고 구했다.

1
2
3
4
5
import math


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

math.gcd로 최대공약수를 직접 구현하지 않고 구했다.


This post is licensed under CC BY 4.0 by the author.