정수론4 [C/C++] 프로젝트 오일러 #94 Almost Equilateral Triangles(수학) Project Euler #94: Almost Equilateral Triangles 문제는 “거의 정삼각형” 성질을 가진 삼각형 중에서 주어진 조건을 만족하는 삼각형의 합을 구하는 문제입니다. 정삼각형은 세 변의 길이가 모두 같은 삼각형입니다. 그러나 이 문제에서는 거의 정삼각형(Almost Equilateral Triangles)을 다룹니다. 거의 정삼각형은 다음 조건을 만족하는 삼각형입니다:1. 두 변의 길이가 같고, 나머지 한 변의 길이가 이와 1 차이가 난다. 예: \(a, a, a+1\) 또는 \(a, a, a-1\) 형태2. 삼각형의 세 변이 정수이고, 넓이도 정수여야 한다.삼각형의 넓이 계산 (헤론의 공식)삼각형의 넓이를 구할 때는 헤론의 공식을 사용합니다.세 변이 \(a, b, .. 2024. 11. 16. [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 다음
