Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- K디지털기초역량훈련
- 회고
- error해결
- avaliable
- AnyObject
- SWIFT
- 생명주기
- copy-on-write
- class
- actionSheet
- weekly calendar
- 제어전송문
- IOS
- 글또
- 내_삶
- uikit
- 바이트디그리
- unrecognized selector sent to class
- 파스칼표기법
- 다짐글
- 연관값
- MyLife
- 글또9기
- Switch
- struct
- ios 개발 강의
- Git
- 코드스니펫
- On branch is up to date with ' '
- 주간 달력
Archives
- Today
- Total
seong_hye, the developer
[백준] 2609번 - 최대공약수와 최소공배수 본문
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
1초 | 128MB | 41418 | 24509 | 20009 | 61.665% |
문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
예제 입력
24 18
예제 출력
6 72
느낀점
두 수의 최대공약수 최소공배수를 생각해 for문으로 만들어 계산하였더니 런타임 에러가 계속 발생했다..
헤매던 끝에 유클리드 호제법을 알게 되었다. //까먹지 말자ㅏㅏ
- 유클리드 호제법이란?
두 수 , 이 때 r은 (0 ≤ r < b) 이고, a ≥ b 이다.
이 때 a 와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다.
아래와 같은 식이 성립하게 된다.
GCD(a, b) = GCD(b, r)
이때 최소 공배수는 두 자연수 즉, a와 b의 곱을 최대 공약수로 나눈 값이다.
시간 초과 당한 코드
import java.util.*; public class Main { public static void main(String args[]) { Scanner input = new Scanner(System.in); int num1,num2; num1 = input.nextInt(); num2 = input.nextInt(); if(num2 > num1) { //num1의 크기를 더 크게 하기 int n = num1; num1 = num2; num2 = n; } //최대공약수 구하기 for(int i = num2; i > 0; i-- ){ // 작은 수 num2에서 1까지 반복 if(num2 % i == 0 && num1 % i == 0){ // 두 수 모두 나눠져 나머지가 0이면 최대공약수 System.out.println(i); break; } } //최소공배수 구하기 for(int j = num1; j < 100000; j++){ // 큰 수 num1에서 큰수까지 반복 if(j % num1 == 0 && j % num2 ==0){ // 두 수 모두 수에서 나눠 0이 되면 최소공배수 System.out.println(j); break; } } } }
작성 코드
import java.util.*; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int num1 = input.nextInt();// 변수 입력 받기 int num2 = input.nextInt(); int max = gcd(num1, num2); System.out.println(max); System.out.println(num1 * num2 / max); // 최소 공배수는 두 자연수의 곱을 최대 공약수로 나눈 값에 해당 } public static int gcd(int num1, int num2) { // 최대공약수 재귀 방식 if (num2 == 0) return num1; return gcd(num2, num1 % num2); // GCD(a, b) = GCD(b, r)이므로 (r = a % b) } }
'알고리즘 코드' 카테고리의 다른 글
[백준] 10430번 - 나머지 (0) | 2021.06.28 |
---|---|
[백준] 1978번 - 소수 찾기 (0) | 2021.06.28 |
Comments