[BOJ/백준/C++] 1934번 최소공배수

2024. 1. 27. 00:05·Coding Test/Baekjoon
728x90
반응형
 

1934번: 최소공배수

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있

www.acmicpc.net


📌 접근 방법

⚡ 최소 공배수 구하는 공식

int LCM(int a, int b){
    return a*b/GCD(a,b);
}
  • a * b / 최대 공약수를 이용하면 구할 수 있음

 

⚡ 최대 공약수 구하는 공식

int GCD(int a, int b){
    int c = a%b;
    while(c!=0){
        a=b; 
        b=c;
        c=a%b;
    }
    return b;
}
  • 유클리드 호제법을 이용해서 구함
    • 유클리드 호제법 : 두 정수 a, b에 대해, a를 b로 나눈 나머지인 c을 이용해서 최종적인 나머지가 0이 될 때까지 위의 과정을 반복하는 것

 

✔ 유클리드 호제법

  • 최대 공약수를 구하는 알고리즘
  • 두 정수 a, b에 대해, a(더 큰 수)를 b(더 작은 수)로 나눠서 나머지를 구한다.
  • 나머지인 r을 이용해서 최종적인 나머지가 0이 될 때까지 위의 과정을 반복한다.
  • 나머지가 0이 됐을 때 마지막 계산에서 나누는 수로 이용된 수가 최대 공약수가 된다.

 

 

✅  Pass Code

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
using namespace std;
int GCD(int a, int b){
    int c = a%b;
    while(c!=0){
        a=b; 
        b=c;
        c=a%b;
    }
    return b;
}
int LCM(int a, int b){
    return a*b/GCD(a,b);
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T,A,B;
    cin>>T;
    for(int i=0; i<T; i++){
        cin>>A>>B;
        cout<<LCM(A,B)<<'\n';
    }

    return 0;
}

 

 

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'Coding Test > Baekjoon' 카테고리의 다른 글

[BOJ/백준/C++] 4134번 다음 소수  (2) 2024.01.27
[BOJ/백준/C++] 2485번 가로수  (1) 2024.01.27
[BOJ/백준/C++] 7785번 회사에 있는 사람  (2) 2024.01.27
[BOJ/백준/C++] 11478번 서로 다른 부분 문자열의 개수  (0) 2024.01.27
[BOJ/백준/C++] 18870번 좌표 압축  (0) 2024.01.27
'Coding Test/Baekjoon' 카테고리의 다른 글
  • [BOJ/백준/C++] 4134번 다음 소수
  • [BOJ/백준/C++] 2485번 가로수
  • [BOJ/백준/C++] 7785번 회사에 있는 사람
  • [BOJ/백준/C++] 11478번 서로 다른 부분 문자열의 개수
예롱메롱
예롱메롱
  • 예롱메롱
    예롱이의 개발 블로그
    예롱메롱
  • 전체
    오늘
    어제
    • 전체보기 (274)
      • 프로젝트 (35)
        • Wedle (12)
        • 인스타그램 클론 코딩 (13)
        • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (10)
      • 인프런 Spring 강의 정리 (79)
        • 스프링 입문 - 코드로 배우는 스프링 부트, 웹 .. (7)
        • Spring 핵심 원리 - 기본편 (9)
        • 모든 개발자를 위한 HTTP 웹 기본 지식 (8)
        • 자바 ORM 표준 JPA 프로그래밍 - 기본편 (11)
        • 실전! 스프링 부트와 JPA 활용1 - 웹 애플리.. (6)
        • 실전! 스프링 부트와 JPA 활용2 - API 개.. (5)
        • 실전! 스프링 데이터 JPA (7)
        • 스프링 MVC 1편 - 백엔드 웹 개발 핵심 기술 (7)
        • 스프링 MVC 2편 - 백엔드 웹 개발 활용 기술 (11)
        • 실전! Querydsl (8)
      • Cloud (3)
      • Spring (6)
        • spring boot (5)
        • 소셜로그인 (1)
      • Docker (2)
      • DevOps (0)
      • Coding Test (114)
        • Programmers (37)
        • Baekjoon (76)
      • KB It's Your Life 6기 (1)
      • CS (18)
        • 알고리즘 (13)
        • 컴퓨터 구조 (1)
        • Operating System (0)
        • Network (0)
        • Database (4)
      • git (1)
      • Language (15)
        • Java (5)
        • C++ (6)
        • Python (4)
    • GITHUB GITHUB
    • INSTAGRAM INSTAGRAM
  • hELLO· Designed By정상우.v4.10.3
예롱메롱
[BOJ/백준/C++] 1934번 최소공배수
상단으로

티스토리툴바