최대 공약수3 [Kotlin] 백준 1850 : 최대공약수 문제 링크 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 해설 모든 자리가 1로 이루어진 두 수의 최대 공약수를 구해야 한다. 우선 모든 자리가 1로 이루어진 수가 어떻게 구성되는지 보자. \(1111\)의 경우에는 다음과 같이 나눌 수 있다. $$1111=11\times 101$$ 또 다른 수인 \(111111\)은 다음과 같이 나눌 수 있다. $$\begin{align*}111111&=11\times 10101\\&=111\times 1001\end{align*}$$ 자세히 보.. 2023. 11. 11. [Kotlin] 백준 2485 : 가로수 문제 링크 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 문제 해설 각 가로수의 거리 간격이 동일해지도록 새로운 가로수를 심어야한다. 단순히 생각하면 각 가로수 사이의 거리를 구해서 거리의 최소값 간격으로 심으면 될 것 같지만 예제 2번의 경우가 반례가 된다. 이 경우에는 각 가로수 사이의 거리가 4, 6, 6이 되어 최소 거리가 4가 된다. 이렇게 되면 2부터 4의 간격으로 나무를 심게 되면 [2, 6, 10, 12, 14, 18]이 되기 때문에 각 가로수 사이의 거리가 일치하지 않는다. 이 문제는.. 2023. 7. 5. [Kotlin] 백준 1490 : 자리수로 나누기 문제 링크 1490번: 자리수로 나누기 첫째 줄에 어떤 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해설 문제에서 이야기하는 N의 0이 아닌 모든 자리수로 나누어 떨어진다는 말은 곧 N의 0이 아닌 모든 자리수의 최소 공배수로 나누어 떨어진다는 말과 같다. 따라서 가장 먼저 0이 아닌 모든 자리수의 최소 공배수를 구해야 한다. 최소 공배수는 최대 공약수를 이용하여 구할 수 있고(코드의 lcm 함수), 최대 공약수는 유클리드 알고리즘을 사용하여 구할 수 있다(코드의 gcd 함수). 최소 공배수를 구했다면 N으로 시작하면서 최소 공배수로 나누어 떨어지는 수를 탐색해야 한다. 이 부분은 N에 10의 거듭제곱을 곱해가면서 반복문으로 나누어 떨어.. 2022. 12. 29. 이전 1 다음
