https://www.acmicpc.net/problem/1256알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론❓문제🔅해석'a'와 'z'의 조합으로 n번째 단어를 출력하는 문제이다.사전에는 알파벳 순서대로 수록되어 있으므로 'a'로 시작하는 문자의 조합으로 계산해본다.입력 : 2 2 6 1. a_ _ _ 'a'로 시작하는 문자의 조합 개수는 남은 3자리수와 남은 'z'의 갯수 3C2이다. 3C2 = 3이므로 'a'로 시작했을 때 3가지의 조합을 만들 수 있다.우리는 6번째(K) 순서를 원하므로 'z'로 시작한다는 것을 알 수 있다. (3C2 1) 결과값을 담는 sb에 'z'를 추가하고2) 'z' 카운트를 하나 감소시킨다.3) K의 값을 조합 수 만큼 감소시킨다. 2. z a _ _위에서 'z'로 ..
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..
https://www.acmicpc.net/problem/14476 알고리즘 분류 : 수학, 정수론, 누적합, 유클리드 호제법❓문제 🔅해석위 문제는 누적합과 유클리드 호제법을 이용하여 풀이해야한다. 먼저 두 수의 최대공약수를 구하는 방법인 유클리드 호제법을 구현한 코드이다.// gcd(a, b) == gcd(b, r) : r = a % bstatic int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a;} 이 유클리드 호제법을 통해 나온 최대공약수를 누적합 배열에 담는다. 8 12 24 36 48예를들어, 입력이 위와 같이 들어왔을 때, 8 ~ 48의 최대공약..
