[프로그래머스] 코딩테스트 입문 : 피자 나눠 먹기(2)

| 문제

머쓱이네 피자가게는 피자를 여섯 조각으로 잘라 줍니다.

피자를 나눠먹을 사람의 수 n이 매개변수로 주어질 때,

n명이 주문한 피자를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면

최소 몇 판을 시켜야 하는지를 return 하도록 solution 함수를 완성해 보세요.

| 제한 사항

1 ≤  n ≤  100

| 입출력 예

n	result
6	1
10	5
4	2

| 풀이 1

public int solution01(int n) {
    int a = n;
    int b = 6;
    int temp = 0;
    while(b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return n/a;
}

| 풀이 2

public int solution01(int n) {
    int a = 1; 
    while(a*6 % n != 0) a++;
    return a;
}

| 해설

문제의 설명이 참 어렵네요.

n명이 주문한 피자를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면 최소 몇 판을 시켜야 하냐니... 

자, 헤매지 말고 피자 나눠 먹기(1) 문제에서 했던 것처럼 숫자를 나열해 봅시다.

n(사람수)	slice(조각)	answer(피자)	전체 조각
1	6	1	6
2	3	1	6
3	2	1	6
4	12	2	12
5	6	5	30
6	1	1	6
7	6	7	42
8	3	4	24

와 정말 정답이 들쪽날쭉하네요. 1,1,1,2,5,1,7,4라니... 

결과로 return 하는 answer만 보면 규칙이 잘 보이지 않지만

침착하고 전체 조각의 개수를 한번 살펴보시면 규칙이 보일 거예요.

바로 n과 6의 최소 공배수가 바로 전체 조각이라는 사실!!

 

최소 공배수라면 유클리드 호제법을 뺄 수 없죠.

두 수를 곱하고 최대공약수를 나눠주면 최소 공배수를 구할 수 있습니다.

그러나, 여기서는 두 수중에 한 수 피자 조각의 개수가 6으로 고정되어 있기 때문에

유클리드 호제법 알고리즘을 사용하지 않아도 결과를 도출할 수 있습니다.

 

여기서는 최대 공약수를 구할 필요가 없고,

6씩 늘어나는 값들 중에서 사람 수 n으로 나눴을 때 나머지가 0인 숫자를 구하기만 하면 됩니다.

그래서 복잡한 유클리드 호제법을 사용하지 않고도 최초 피자가 한판 있다고 가정한 다음

6*anwer를 n으로 나눴을 때 나머지가 0이 될 때까지 answer를 늘려주는 방법을 사용할 수도 있어요.

풀이 1은 유클리드 호제법으로, 풀이 2는 간편한 방법으로 작업했으니 참고해 주세요.