본문 바로가기

유클리드 호제법4

[자바] 백준 1684 - 같은 나머지 (java) 목차 문제 : boj1684 필요 알고리즘 정수론, 유클리드 호제법 의외로 GCD 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N이 2인 경우만 생각해보자. 문제에서 입력된 어떠한 정수 2개를 N1, N2라고 하면, R1==R2가 되려면 아래처럼 식이 전개될 것이다. 따라서 N2-N1 즉, 두 수의 차이는 정수인 Q2-Q1과 D의 곱이 된다. 이 때 Q2-Q1이 뭔지는 모르겠지만 아무튼 정수인 D가 가장 크.. 2023. 7. 25.
백준 9613 자바 - GCD 합 (boj 9613 java) 문제 : boj9613 우선 모든 쌍을 확인하는게 이 가능할지 확인해보자. n은 최대 100 이므로 모든 쌍을 확인할 경우 O(n^2)이 필요하고, 총 t개의 테스트케이스가 존재하므로 O(100*100^2) 이므로 충분히 가능하다. 그럼 뭐 어렵게 생각할 것 없이 무지성으로 모든 쌍을 확인해보면 된다. 모든 쌍 확인은 예를들어 배열의 길이가 5일 경우 인덱스는 0,1,2,3,4가 존재할 것이다. 그럼 0-1, 0-2, 0-3, 0-4, 1-2. 1-3. 1-4, 2-3, 2-4, 3-4 와 같이 확인하면 된다. 코드의 27~28line을 참고해보자. 그리고 모든 쌍에 대해 각각 GCD를 구해 그 결과를 더해주면 되는데, GCD의 경우 유클리드 호제법을 사용하면 빠르게 구할 수 이다. 유클리드 호제법은 검.. 2022. 4. 6.
백준 14881 자바 - 물통 문제 (BOJ 14881 JAVA) 문제 : https://www.acmicpc.net/problem/14881 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/14800/BOJ_14881.java 처음엔 별 생각없이 brute force 정도로 생각했는데, 시간복잡도가 아닌 것 같아 다른 방법을 찾아봤다. 결론은 최대공약수 문제이다. 일단 되는 경우와 안되는 경우에 대해 생각해보자. 1. 일단 c가 a와 b 둘 모두보다 크다면 아예 불가능하다. (코드의 max>=c) 2. c가 a나 b와 동일하다면 당연히 가능하다. (코드의 a==c || b==c) 3. 다음으로 a,b의 최대공약수가 c의 공약수라면 가능하다. (코드의 c%gcd==0) 4. 마지막으로 a와 b가 서.. 2021. 10. 25.
백준 23276 자바 - Locust Locus (BOJ 23276 JAVA) 문제 : https://www.acmicpc.net/problem/23276 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23200/BOJ_23276.java 결국 k개의 입력 중 y + (c1과 c2의 최소공배수) 의 최소값을 찾으면 된다. 최소공배수는 유클리드 호제법을 통해 구했다. 2021. 10. 22.

티스토리툴바