반응형 정수론3 [C/C++] 백준 #2168 타일 위의 대각선(정수론) 이번 문제는 정수론(number theory)을 알면 쉽게 해결할 수 있습니다. 정수론에서 가장 기본이 되는 것 중에 하나가 최대 공약수(GCD; Greatest Common Divisor)입니다. 최대 공약수를 구해서 문제를 해결할 수 있습니다. 문제의 링크는 다음과 갈습니다. https://www.acmicpc.net/problem/2168 2168번: 타일 위의 대각선 첫째 줄에 가로의 길이 xcm와 세로의 길이 ycm가 주어진다. x와 y는 1,000,000,000 이하의 자연수이다. x와 y사이에는 빈칸이 하나 이상 있다. www.acmicpc.net 대각선이 그려진 타일의 개수를 구하는데, 어떻게 하면 될까요? 일단 아래의 그림을 가지고 이야기를 해보죠. 가로가 16, 세로가 5개인 타일들입니.. 2023. 4. 12. [Python] 백준 #1684 같은 나머지(정수론) 이번 문제는 주어진 숫자들에 대해서 나머지가 같은 수가 되는 나눔수 중 최대의 정수를 찾는 것입니다. 나머지가 같다는 것은, 숫자들의 차이에 대한 최대공약수를 구하는 것과 같습니다. \[ Find~ maximum~ such~ D~ that~ \forall i ~ a_i ~mod ~D = k \Longleftrightarrow gcd( a_i - min(a) ) \] 음수를 피하기 위해서 주어진 수 중에 가장 작은 수를 찾습니다. 그리고 나머지 수 중에 가장 작은 수와 같은 경우를 제외하고, 그 차이를 기록합니다. 마지막으로 그 차이들의 수열의 최대 공약수를 구합니다. 다음은 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. """ baekjoon #1684 - by Aubrey Choi - creat.. 2022. 9. 29. #1214 쿨한 물건 구매(정수론) 이번 문제는 정수론을 잘 이해하셔야 풀기 편한 문제입니다. 보통 확장 유클리드 소거법이라는 것을 이용하게 되는데요. 확장 유클리드 소거법은 두개의 수가 주어졌을 때, 유클리드 소거법을 이용해서 최대공약수를 구하는 과정을 거꾸로 하는 것입니다. 예를 들어서 12와 20의 최대공약수를 구하는 과정을 볼께요. \[ 8 = 20 - 12 \] \[ 4 = 12 - 8 \] 로 12와 20의 최대공약수는 4임을 알 수 있습니다. 그리고 이 식을 거꾸로 가게 되면, \[ 4 = 2 \times 12 - 20 \] 을 얻을 수 있죠. 이렇게 최대공약수를 구하는 파라미터터 (2, -1)을 얻는 것이 확장 유클리드 소거법의 목적입니다. 아래의 소스는 확장 유클리드 소거법을 프로그램한 것입니다. void xgcd(long.. 2020. 1. 7. 이전 1 다음 728x90
