2 분 소요

최대공약수와 최소공배수

solved_ac[Class2] 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6
72

문제 해석

유클리드 호제법으로 최대공약수와 최소공배수를 구하면 된다.

유클리드 호제법

a와 b라는 자연수가 있다.

image

최대공약수

  • b로 a를 나눈 나머지를 r값으로 지정해준다.
  • b값을 a값으로 업데이트 시켜주고 나머지 값인 r을 b값으로 업데이트 시켜준다.
  • 이 과정을 나머지가 0이 될 때까지 반복한다.
  • 0이 되었을때의 b값이 최대공약수이다.

최소공배수

  • 위의 과정에서 맨 처음 입력 받은 a와 b값을 곱한다.
  • 최대공약수로 나눈다.
  • 그 값이 최소공배수이다.

결론

최대공약수 : 2

최소공배수 : 10 * 12 // 2 = 60

풀이

  • 자연수 입력 받음

  • 최대공약수 함수 gcd를 선언

  • 유클리드 호제법에 따라서 a와 b가 나누어질때까지 계속 돌릴것이기 때문에 재귀함수로 모델링

  • a와 b가 나누어지게 되면 재귀함수 호출은 멈추어야 하기 때문에 if문을 걸어준다.

  • 그게 아니라면 old b값을 new a값으로 업데이트 시키고 new b값에는 old a와 old b의 나머지 값으로 업데이트 시켜줘서 재귀함수 호출해준다.

  • 최대공약수 함수 result 선언

  • a와 b 그리고 최대공약수를 곱한 값을 리턴값으로 설정해준다.

import sys

M, N = map(int, sys.stdin.readline().split())

def gcd(M, N):
    if M % N == 0:
        return N
    else:
        return gcd(N, M % N)

def result(M, N, gcd):
    sum = 1
    sum *= M // gcd
    sum *= N // gcd
    sum *= gcd
    return sum

        
res_gcd = gcd(M, N)
res = result(M, N, res_gcd)
print(res_gcd)
print(res)

다짐

어제 다짐을 하자마자 변수가 생겼다.. 오늘은 약속이 생겨서 핑계 안대고 다음날 두배를 포스팅 하겠다..

어제의 다짐

학기가 끝난지 약 1주일이 지났다. 많이 놀았고 많이 나태해졌기 때문에 9월까지 내가 목표한 바를 이루기 위해서는 지금부터 달려야한다.

class 2는 20문제가 남았기 때문에 하루에 5문제씩 4일 동안 끝낼것이다.

현재 시각 오후 2시 20분

복싱 가서 운동을 하고 알바를 가서 11시에 마치고 나서 연구실에 바로 온다.

목표한 5문제를 풀고 새벽 3시쯤에 퇴근

취침 후 아침 9시 전까지 연구실 출근

복싱 코치님과 일요일에 술 약속이 있으니깐 가기 전 까지 5문제를 다 풀고 블로그 포스팅까지 완료 후 간다.

월요일 부터는 친구들과 백준 스터디가 다시 시작하니 월요일에 class 2 5문제와 class 3 1문제를 푼다

화요일도 월요일과 마찬가지

수요일부터는 class 3 친구들이 이미 푼 문제를 나혼자 추가해서 다시 푼다 여기서 부터는 하루에 나혼자 푸는 문제 3문제 + 스터디 1문제

미해결 문제는 37문제니깐 1주일에 나 혼자 푸는 문제 15문제 + 스터디 5문제

최소 2주안에 끝낸다.

이 목표대로 간다면 7월 10일까지 class 3 완료가 된다.

그때와서 이 게시글을 다시 보겠다.

댓글남기기

참고