[프로그래머스 / C++] Lv 0. 피자 나눠 먹기 (2)

문제

문제링크

풀이

유클리드 호제법을 이용해 문제를 해결할 수 있다.
gcd(a, b) = gcd(b, a % b)

제한사항
1 ≤ n ≤ 100

입출력 예
n result
6 1
10 5
4 2

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    if (n % 6 == 0)
        answer = n / 6;
    else {
        if (n > 6) 
            answer = n / 6 + n % 6;
        else if (n < 6 && n >= 1) 
            answer = 6 - n;
    }
    
    return answer;
}

위 코드는 무작정 문제설명과 입출력 예만을 보고 작성한 코드이다. 그래서다음과 같이 생각했다.

• 케이스 2가지

1. 나누어 먹을 사람의 수 n이 6으로 나누어 질 경우
2. 나누어 먹을 사람의 수 n이 6으로 나누어지지 않는 경우

• n이 6보다 클 경우: answer = 몫 + 나머지
• n이 6보다 작을 경우: answer = 6 - 나머지

이렇게 입출력 예만을 보고 테스트를 돌린 결과...

다음과 같이 테스트 케이스 전체를 통과하는데 실패했다. 그래서 문제의 원인이 뭔지 곰곰히 생각해 본 결과 최대공약수와 관련이 있는 것 같아 유클리드 호제법을 떠올렸는 데 다른 분들이 작성한 코드를 본 결과 내 생각이 맞았다. 그래서 수정한 코드는 다음과 같다.

수정 코드

#include <string>
#include <vector>

using namespace std;

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

int solution(int n) {
    int answer = 0;
    int m = gcd(n, 6);
    
    answer = n / m;
    
    return answer;
}

결과