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

코딩 테스트 - 프로그래머스

코딩 테스트 - 프로그래머스

피자 나눠 먹기(2)

 

문제

머쓱이네 피자가게는 피자를 여섯 조각으로 잘라 줍니다. 피자를 나눠먹을 사람의 수n 이 매개변수로 주어질 때, n명이 주문한 피지를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면 최소 몇 판을 시켜야 하는지를 return 하도록 solution 함수를 완성해보세요.

 

문제의 원리

이 문제의 핵심 원리는 '최소 공배수'를 이용하는 것입니다. 최소 공배수는 두 개 이상의 자연수의 공배수 중 가장 작은 수 입니다. 여기서 공배수란 두 개 이상의 자연수의 공통적인 배수를 말합니다.

 

피자는 6조각으로 나눠어져 있으므로, 이를 n명이 공평하게 나누어 먹기 위해서는 피자 조각의 총 갯수 n의 배수가 되어야 합니다.

 

따라서 피자의 조각 = 6 과 사람의 수 =  n의 최소 공배수를 찾아 그 값에서 6을 나누면, 공평하게 먹을 수 있는 피자의 갯수를 알 수 있습니다.

 

문제의 원리

 

최소 공배수를 구하기 위해서 최대 공약수를 구해야합니다, 그 이유는 두 수의 곱이 두 수의 최대 공약수와 최소 공배수의 곱이 같다는 원리 때문에 최대 공배수를 구해야합니다.

 

최소 공배수는 두수의 곱 에서 최대 공배수를 나눈 값이 됩니다.

문제의 원리

그럼 문제 풀이 순서가 다음 같이 나옵니다.

1. 최대 공약수 구하기
2. 최소 공배수 구하기
3. 최소의 피자 판 구하기

문제 풀이

Python

• 각 함수 생성
  

  def 최대공약수(a, b):
      while b != 0:
          a, b = b, a%b
      return a
  
  def 최소공배수(a,b):
      return a * b // 최대공약수(a,b)
  
  def solution(n):
      return 최소공배수(n,6) // 6​

• 하나 함수로 조합
  

  def solution(n):
      a, b = n, 6
      while b != 0:
          a, b = b, a % b
      return (n * 6) // a​

• 최대 공약수 함수 사용하기
  

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

• 최소 공약수 함수 사용하기
  

  import math
  
  def solution(n):
      return math.lcm(n, 6) // 6​

JavaScript

• 각 함수 생성
  

  function gcd(a, b) {
      while (b != 0) {
          let temp = a;
          a = b;
          b = temp % b;
      }
      return a;
  }
  
  function lcm(a, b) {
      return a * b / gcd(a, b);
  }
  
  function solution(n) {
      return lcm(n, 6) / 6;
  }
  
  console.log(solution(10));​

• 하나 함수로 생성
  

  function solution(n) {
      let a = n, b = 6;
      while (b != 0) {
          let temp = a;
          a = b;
          b = temp % b;
      }
      return (n * 6) / a;
  }
  
  console.log(solution(10));​

자바스크립트는 최대 공약수, 최소 공배수 구하는 함수가 없습니다.

 

출처

https://school.programmers.co.kr/learn/courses/30/lessons/120815