문제 내용
다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어지는 가장 작은 자연수이다.
서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.
입출력
1. 입력
첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.
2. 출력
첫째 줄에 적어도 대부분의 배수를 출력한다.
예제
입력 | 출력 |
---|---|
30 42 70 35 90 | 210 |
1 2 3 4 5 | 4 |
30 45 23 26 56 | 1170 |
3 14 15 92 65 | 195 |
풀이
처음 문제를 봤을 때 최소공배수를 이용하는 문제라는 것을 바로 알게 됐다.
문제 해결 방식으로 공약수로 세 수를 동시에 나눠서, 공약수와 나눈 서로소를 곱하는 것을 채택했다.
여기서 문제가 최소공배수는 일단 '두 자연수'의 공통된 배수중 가장 작은 배수이므로 세 수를 동시에 하는 방식은 잘못됐다.
최소공배수 너무 오랜만이야 ㅠㅠ
따라서 우선 두 수의 최소공배수를 먼저 구한 결과와 나머지의 최소공배수를 구하는 방식으로 해결했다.
/*
3개의 최소공배수를 구하면 된다.
1. 공약수로 서로소가 나올 때 까지 나눈다.
2. 나눈 공약수와 서로소를 모두 곱해준다.
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> numbers = new ArrayList<>(); //5개의 주어진 정수
int aCommonMultiple; //최소공배수
int result = 1000000; //결과
//문자열 => 정수
for (String e : br.readLine().split(" ")) {
numbers.add(Integer.parseInt(e));
}
br.close();
for (int i = 0; i < numbers.size() - 2; i++) {
for (int j = i + 1; j < numbers.size() - 1; j++) {
for (int k = j + 1; k < numbers.size(); k++) {
int first = numbers.get(i); //첫번째수
int second = numbers.get(j); //두번째수
int third = numbers.get(k); //세번째수
//1, 2번째수의 최소공배수
aCommonMultiple = getCommonMultiple(first, second);
//이전 결과, 3번째수의 최소공배수
aCommonMultiple = getCommonMultiple(aCommonMultiple, third);
//결과가 최소일경우 result 변경
if (aCommonMultiple < result) {
result = aCommonMultiple;
}
}
}
}
System.out.println(result);
}
//두 수의 최소공배수
//변수 : 소수, 두개의 수
public static int getCommonMultiple(int first, int second) {
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};//소수
Stack<Integer> aCommonDivisor = new Stack<>(); //공약수
int temp; //공약수의 곱
//소인수로 나누기
for (int primeIndex = 0; primeIndex < primes.length; ) {
//나누어 떨어지면
if (first % primes[primeIndex] == 0 && second % primes[primeIndex] == 0) {
//공약수를 저장
aCommonDivisor.add(primes[primeIndex]);
//소인수로 나눈 결과를 다시 저장
first /= primes[primeIndex];
second /= primes[primeIndex];
}
//아닐경우 다음 소인수
else {
primeIndex++;
}
}
temp = 1; //초기화
for (int a : aCommonDivisor) {
temp *= a;
}
aCommonDivisor.clear();
return temp * first * second;
}
}
다른 사람들은 어떻게 풀었는지 궁금했는데 완전 탐색을 쓰는 사람도 있고 나처럼 최소공배수를 구하는데 훨씬 깔끔한 사람도 있었다.
완전 탐색은 최후의 보루로 생각해서 안 했지만, 훨씬 깔끔하게 최소공배수를 구한 코드는 신기해서 다른 사람들 것 전부 본 결과 코드가 똑같았다.
그 이유는 'java 최소공배수'를 구글링 하고 알게 됐다.
배신당한 느낌... 내 시간 돌려줘
public class Main {
public static void main(String[] args) {
System.out.println(lcm(4, 6)); // 12
// 세 숫자의 최소공배수 구하기
long result = lcm(45, lcm(120, 75));
System.out.println(result); // 1800
// 네 숫자의 최소공배수 구하기
result = lcm(112, lcm(113, lcm(114, 119)));
System.out.println(result); // 12263664
}
// 최소 공배수 계산 메서드
// 최소공배수는 엄청나게 큰 숫자가 나올 수도 있기에
// long형으로 다루어야 합니다.
public static long lcm(long a, long b) {
int gcd_value = gcd((int) a, (int) b);
if (gcd_value == 0) return 0; // 인수가 둘다 0일 때의 에러 처리
return Math.abs((a * b) / gcd_value);
}
// 최대 공약수 계산 함수; 최소 공배수 계산에 필요함
// 최대 공약수는 그리 큰 숫자가 나오지 않기에 int형으로
public static int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return Math.abs(a);
}
}
블로그에 있는 코드를 그대로 스크랩해봤다.
내 코드는 주어지는 수의 최댓값이 100이기 때문에 소수의 범위를 지정해 놓고 공약수와 서로소를 곱하는 방식으로 푼 반면에, 스크랩해온 코드는 두 수가 나누어 떨어질 때 나눈 값(최대공약수)을 두 수 의 곱에서 나눈 방식이다.
이렇게 할 경우 두 수를 지수로 풀어썼을 때 공통된 부분이 나눠지므로 최대공약수가 구해지는 것이다.
21과 6을 예로 들면
21 % 6 = 3 -> 6 % 3 = 0 따라서 gcd의 리턴 값은 3이 된다.
21 * 6 / 3 = 42 따라서 두 수의 최소공배수는 42가 되는 것이다.
위 식을 지수로 풀어쓰게되면
21 = 3 * 7
6 = 2 * 3
두 수의 최대공약수는 3
21 * 6 = 2 * 3^2 * 7으로 겹치는 수는 3이다. 따라서 3을 나누게 되면 최소공배수가 나오게 된다.
오래간만에 풀어본 수학이라 설명을 잘 못했지만 혼자 생각해서 결과를 냈다는 것에 만족한다.
구글링 해볼걸
kotlin code
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val numbers = ArrayList<Int>() //제시되는 입력
var aCommonMultiple = 0 //최소공배수
var result = 1000000 //결과값
//문자열 -> 정수
for (a in br.readLine().split(" ")) {
numbers.add(a.toInt())
}
br.close()
for (i in 0 until numbers.size - 2) {
for (j in i + 1 until numbers.size - 1) {
for (k in j + 1 until numbers.size) {
var first = numbers[i] //첫번째 수
var second = numbers[j] //두번째 수
var third = numbers[k] //세번째 수
//1, 2번째수의 최소공배수
aCommonMultiple = getCommonMultiple(first, second)
//이전 결과, 3번째수의 최소공배수
aCommonMultiple = getCommonMultiple(aCommonMultiple, third)
//결과가 최소일경우 result 변경
if (aCommonMultiple < result) {
result = aCommonMultiple
}
}
}
}
print(result)
}
//두 수의 최소공배수를 리턴
fun getCommonMultiple(firstParam: Int, secondParam: Int): Int {
var first = firstParam //val -> var
var second = secondParam
val primes = arrayOf(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)
val aCommonDivisor = Stack<Int>() //공약수를 저장
var temp = 1 //공약수의 곱
//소인수로 나누기
var i = 0;
while (i < primes.size) {
//나누어 떨어지면
if (first % primes[i] == 0 && second % primes[i] == 0) {
//공약수를 저장
aCommonDivisor.add(primes[i])
//나눈 값으로 재실행
first /= primes[i]
second /= primes[i]
} else {
i++
}
}
temp = 1
for (a in aCommonDivisor) {
temp *= a
}
aCommonDivisor.clear() //스택 비우기
//공약수 * 서로소 * 서로소
return temp * first * second
}
'코딩테스트 > 백준' 카테고리의 다른 글
1193 / 분수찾기 (0) | 2022.06.13 |
---|---|
1157번 / 단어공부 (0) | 2022.06.13 |
1032번 / 명령프롬포트 (0) | 2022.06.13 |
2475번 / 검증수 (0) | 2022.06.13 |
2338번 / 긴자리계산 (0) | 2022.06.13 |