유클리드호제법2

• 

  백준 3036 - 링 JAVA 해당 문제는 엄청 쉬운 문제였다. 기약분수 -> 최대공약수 구하기 문제로 보면 편하다. 1. 첫 번 째 원을 한바퀴 돌리면 나머지 원도 첫 번째 원의 둘레만큼 돌아야 하는구나 2. 결국 기약분수로 표시하라는 것은 그냥 첫 번째 원 둘레 / 나머지 원 둘레겠구나 3. 기약분수는 최대공약수로 분자,분모를 나누면 되겠구나. 4. 유클리드 호제법으로 최대공약수 메서드 구현해야지! package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Boj_3036 { public static void main(.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 15.

• 

  백준 2981 - 검문 JAVA(feat. koosaga님) 해당문제는 한 15분 고민하다가 과감하게 구글링을 한 문제이다. 결국 유클리드 호제법을 사용하는 문제인데 그 전에 유도식이 존재한다. A와 B를 나눠서 나머지가 같다라는 말을 식으로 표현하자면 A = a*M + spare B = b*M + spare -> A - B = M * (a - b) 가 성립된다결국 M*(a-b)을 구하는 문제에 해당하므로 M*(a-b)의 약수들의 집합이 답이다. A, B, C가 있다면 A와 B의 M*(a-b)값과 B-C의 값인 M*(b-c)의 최대공약수(gcd)를 계속 구하여 그 최대공약수의 약수의 집합을 오름차순으로 나열하면 되는 문제이다. 유클리드 호제법의 경우 위키피디아를 보면 잘 나와 있으므로 참고하시라! https://ko.wikipedia.org/wiki/%EC%9C%.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 14.