최대공약수
-
[백준 3036] - [수학 최대공약수] - 링 (JAVA)알고리즘/수학 2018. 12. 4. 11:14
문제 링크 : https://www.acmicpc.net/problem/3036 이문제는 높은 정답률을 자랑한다.그렇다는건 너무 쉽다는 거고 깊은 생각을 할 필요가 없는 문제다. 4 12 3 8 4 예제와 같이 12 3 8 4가 입력이 되고 첫번째 링인 12가 한바퀴 돌았을때 다른 링들은 볓바퀴 돌것이냐 라는 말이다. 그럼 12와 각 링들의 최대 공약수를 구해서 나눠 주면 되겠구나 생각했다. 최대공약수 나눈다면 자연스럽게 기약분수로 만들어 질것이다. 12와 3의 최대 공약수는 3 -> 12 / 3 + "/" +3 / 3 하면 4/112와 8의 최대 공약수는 4 -> 12 / 4 + "/" + 8/4 하면 3/212와 4의 최대 공약수는 4 -> 12 / 4 + "/" + 4/4 하면 3/1 다 구했다 아..
-
[백준 2981] - [수학 최대공약수] - 검문 (JAVA)알고리즘/수학 2018. 12. 4. 11:07
문제 링크 : https://www.acmicpc.net/problem/2981 이 문제는 정답률에서도 나오듯이 극악의 문제이다. 왜 극악이라 하냐면 쓸데없는데서 시간을 낭비 했기에 극악의 문제로 생각한다. 6 34 38 총 3개의 수가 주어지고 종이에 적은수 M으로 나누었을때 나머지가 모두 같게 되는 모든 M을 찾아 보기위해 노력 해봤다. 처음에는 시간초과가 발생했다. 시간초과를 발생하게한 방식은 다음과 같다. 입력 받은 수의 배열 arr에서 인덱스 1번부터 arr.length-2 까지 반복하면서 i 기준 arr[i] - arr[i-1] , arr[i+1] - arr[i] 두 수의 최대 공약수를 구하고 그 최대 공약수중에서 제일 작은 최대 공약수의 약수를 반환했다. 결과는 제대로 나왔다. 하지만 시간 ..
-
[백준 1850] - [ 수학 최대공약수 ] - 최대공약수 (JAVA)알고리즘/수학 2018. 12. 4. 01:42
문제 링크 : https://www.acmicpc.net/problem/1850 이 문제는 어려움을 가장한 쉬운 문제이다. 낮은 정답률에 겁을 먹고 다들 시도를 하지 못한거 같다. 예제 입력 3번의 값이 이 문제는 변태적인 문제다 겁을 먹어라 하는거 같다. 500000000000000000 500000000000000002예제 입력 1번의3 4로 보면 111과 1111의 최대 공약수를 구하면 되겠구나!! 하겠지만 예제 입력 3번은 어떻게 하라고.. 1을 저만치 쓰라고?? 하면서 겁을 먹게 하는거 같다. 그냥 단번에 아 낚시구나 생각했고 두 수의 최대 공약수를 구해보았다. 예제 입력 1 의 입력값 3 4의 최대 공약수는 1예제 입력 2 의 입력값 3, 6의 최대 공약수는 3예제 입력 3의 입력값 무진장 큰..