백준 17087 숨바꼭질6 c++ 유클리드 호제법

이 문제는 수빈이의 현재 위치와 동생들의 위치사이의 간격끼리의 GCD(최대공약수)를 구하는 문제이다 그래서 GCD를 구하는 알고리즘을 잘짜야지 통과가 되는데 I=2부터부터 해당 수 까지 일일히 찾으니 너무 오래걸린다 구글링해보니 GCD를 구하는 유명한 알고리즘 유클리드 호제법이라는게 있어서 사용해보았다 유클리드 호제법이란 수 A,B 가 있을때(A>B) A%B한 값이 0이 될때까지 반복하면 A값이 최대공약수라는 알고리즘이다 증명은 딱히 필요없고 어떻게 그게 되는지 확인해보겠다 A=12, B=8이라 가정 First step A=12, B=8 Second step A=12%8, B=8 -> A=4, B=8 -> A=8, B=4 Third step A=8%4, B=4 -> A=0, B=4 -> A=4, B=0 ..
코딩 테스트/백준 2022. 2. 22. 16:55
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/12   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함