코딩테스트/백준
[코테] 백준 3955번 : 캔디 분배 (java)
https://www.acmicpc.net/problem/3955알고리즘 분류 : 수학, 정수론, 확장 유클리드 호제법❓문제🔅해석확장 유클리드 호제법 알고리즘을 이용한다. (공식 : ax+by=gcd(a,b))방정식에 적용할 a, b, c를 생각해보자면, a와 b는 입력값인 인원수, 한 봉지에 든 사탕 개수로 둘 수 있다.axby인원수인당 나눠줄 사탕 수한 봉지에 든 사탕 수사탕 봉지수ax + 1 = by 아래와 같이 항 정리를 한다.-ax + by = 1 여기서 주의할 점은, 나머지 정의가 0 그래서 a, b에 음수가 들어오지 않도록 x가 음수 값을 가지게 한다.a(-x) + by = 1 이제 확장 유클리드 호제법을 통해 s, t, r 값을 구한다.public static EGResult egcd(l..
