유클리드 호제법9 [백준] 2485번 - 가로수 [Java] https://www.acmicpc.net/problem/2485 1. 아이디어 가로수의 간격이 되도록 새로 심어야 하는 가로수는 현재 가로수의 간격의 최대공약수의 최솟값을 구하면 구할 수 있다.2. 문제풀이 첫 두 가로수의 최대공약수를 먼저 구한 후 이를 기준 삼아 다른 두 가로수의 간격과 비교하며 최솟값을 찾는 방식으로 구현했다. 각 가로수를 나머지 모든 가로수와 비교할 필요없이 인접한 두 가로수만으로 비교해도 돼서 한번의 반복문으로 구할 수 있다. 필요한 총 가로수는 (마지막 가로수의 위치 - 첫 가로수의 위치) / (가로수의 간격) + 1 로 구할 수 있는데 이미 심어진 가로수가 N개이므로 N을 빼면 새로 심어야하는 가로수를 구할 수 있다.3. 코드 import java.io.*;public c.. 2025. 2. 1. [백준] 17087번 - 숨바꼭질 6 [Java] https://www.acmicpc.net/problem/17087 1. 아이디어 유클리드 호제법을 활용해 최대 공약수를 구하는 방법으로 해결할 수 있다. 동생들의 위치는 수빈이의 위치에서 D의 배수만큼 더하거나 뺀 값들이므로 수빈이의 위치에서 동생들의 위치를 뺀 값들의 최대 공약수를 구하면 된다.2. 문제풀이 첫 번째 동생과 수빈이의 위치 차를 기준으로 다른 동생들과의 최대공약수를 반복해서 계산하며 갱신하는 방식으로 구현했다. 이때 음수가 나올 수 있어서 모든 차는 절댓값을 씌워서 계산했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOExcept.. 2025. 1. 22. [백준] 1735번 - 분수 합 [Java] https://www.acmicpc.net/problem/1735 1. 아이디어 두 분수의 합을 기약분수로 만드려면 통분 이후 유클리드 호제법으로 약분을 하면 간단하게 해결할 수 있다.2. 문제풀이 통분으로 두 분수의 덧셈을 먼저 해주고 분자, 분모의 최대 공약수로 분자, 분모를 나눠주는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWrit.. 2024. 12. 4. [백준] 9613번 - GCD의 합 [Java] https://www.acmicpc.net/problem/9613 1. 아이디어 GCD의 쌍은 유클리드 호제법을 활용하면 간단하게 구할 수 있다.2. 문제풀이 중복이 가능하기 때문에 반복문에서 유클리드 호제법으로 최대 공약수를 반복해서 구하면 간단하게 해결할 수 있다.이때 최대 공약수의 합은 int형 오버플로우가 발생할 수 있는 점에 주의해야 한다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.i.. 2024. 12. 4. [백준] 12779번 - 상품 is 뭔들 [Java] https://www.acmicpc.net/problem/12779 1. 아이디어 약수의 개수가 홀수인 숫자는 제곱수라는 점을 활용한다.2. 문제풀이 4, 9, 16 같은 제곱수만 약수의 개수가 홀수가 되므로 해당 범위에 포함된 제곱수를 찾은 후 유클리드 호제법으로 기약분수로 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter.. 2024. 12. 3. [백준] 5347번 - LCM [Java] https://www.acmicpc.net/problem/5347 1. 아이디어 유클리드 호제법을 이용해서 최소 공배수를 간단하게 구할 수 있다.2. 문제풀이 유클리드 호제법으로 최대 공약수를 구하는 gcd 메서드를 작성하고 gcd를 통해 최소 공배수를 구할 수 있는 lcm 메서드를 작성하는 방식으로 구현했다.최소 공배수를 구하는 과정에서 int형 오버플로우가 날 수 있는 점만 주의해서 구현하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(.. 2024. 12. 3. [백준] 13241번 - 최소공배수 [Java] https://www.acmicpc.net/problem/13241 1. 아이디어 유클리드 호제법을 이용해서 최소 공배수를 간단하게 구할 수 있다.2. 문제풀이 유클리드 호제법으로 최대 공약수를 구하는 gcd 메서드를 작성하고 gcd를 통해 최소 공배수를 구할 수 있는 lcm 메서드를 작성하는 방식으로 구현했다.문제 조건에서 long 타입을 사용하라고 한 점만 참고해서 구현하면 간단하게 해결할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader.. 2024. 12. 3. [백준] 1934번 - 최소공배수 [Java] https://www.acmicpc.net/problem/1934 1. 아이디어 유클리드 호제법을 이용해서 최소 공배수를 간단하게 구할 수 있다.2. 문제풀이 유클리드 호제법으로 최대 공약수를 구하는 gcd 메서드를 작성하고 gcd를 통해 최소 공배수를 구할 수 있는 lcm 메서드를 작성하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWr.. 2024. 12. 3. [백준] 2609번 - 최대공약수와 최소공배수 [Java] https://www.acmicpc.net/problem/2609 1. 아이디어 유클리드 호제법을 이용해서 최대 공약수와 최소 공배수를 간단하게 구할 수 있다.2. 문제풀이 유클리드 호제법으로 최대 공약수를 구하는 gcd 메서드를 작성하고 gcd를 통해 최소 공배수를 구할 수 있는 lcm 메서드를 작성하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); St.. 2024. 12. 3. 이전 1 다음
