정화 코딩

https://www.acmicpc.net/problem/13172 이 문제의 핵심을 정리하면 아래와 같다. 기약분수 a/b를 다음과 같이 하나의 정수로 표현할 수 있다.  이 때 X는 1,000,000,007과 같은 큰 소수이다.b^(-1)은 b의 모듈러 곱셈에 대한 역원인데, 다음과 같이 계산할 수 있다.  이 정도만 알면 문제를 풀 수 있다. 이제 구체적으로 어떻게 구현할지 생각해보자.한 줄에 분모와 분자 순서대로 한 쌍의 분수가 들어온다. 각 분수에 대해 a * b^(-1) mod X 를 구하면 된다. 그리고 모든 값들을 마치 확률을 더하듯 그냥 더해주면 된다.  내가 헷갈렸던 점은 기약분수 a/b에 대해서 저렇게 계산해야 된다고 하길래 들어온 분모와 분자에 대해서 우선 기약분수 형태로 만들어줘야..

https://www.acmicpc.net/problem/23758 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; priority_queue pq; for (int i = 0; i > x; pq.push(x); } int tmp = n / 2; while (tmp--) pq.pop(); int cnt = 0; while (1) { int cur = pq.top(); pq.pop(); int nxt = cur / 2; ..

https://www.acmicpc.net/problem/1024 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, l; cin >> n >> l; for (int k = l; k = 0 && tmp % 2 == 0) { int a = tmp / 2; for (int i = 0; i 길이가 100 이하인 수열에서만 찾으면 되므로 가능한 모든 수열의 길이에 대해서 연속 수열을 찾아보면 된다.식을 정리하면 다음과 같다. 주의할 점은, 음이 아닌 정수 리스트여야 하므로 tmp >= 0을 체..

https://www.acmicpc.net/problem/32649 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a, b, k; cin >> a >> b >> k; vector ans; ans.push_back(a); ans.push_back(b); for (int i = a + 1; i = k) { for (int i = 0; i 캐어려운 정수론 문제인줄 알았는데 그냥 브루트포스 문제였다 ㅎㅎ;;핵심 포인트는 d는 A의 배수이면서 B의 약수여야 한다는 것이다. 그런데 A와 B의 범위가 그렇게 ..

https://www.acmicpc.net/problem/10830 #include #include using namespace std;int n;long long b;int mod = 1000;vector> mpow(vector> a, long long c) { vector> res(n, vector(n)); if (c == 1) { return a; } else if (c % 2 == 0) { vector> tmp = mpow(a, c / 2); for (int i = 0; i > tmp = mpow(a, c - 1); for (int i = 0; i > n >> b; vector> a(n, vector(n)); for (i..

https://www.acmicpc.net/problem/1629 #include using namespace std;long long divpow(long long a, long long b, long long c) { if (b == 1) return a % c; long long tmp = divpow(a, b / 2, c) % c; if (b % 2 == 0) return (tmp * tmp) % c; else return (((tmp * tmp) % c) * (a % c)) % c;}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long a, b, c; cin >>..

솔브닥 class 4+ 풀고 있었는데 거기에 피보나치 수 6 문제가 있길래 이참에 피보나치 수 문제를 쭉 풀어볼까 한다. 피보나치 수 (백준 2747번)https://www.acmicpc.net/problem/2747 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector fib(n + 1); fib[0] = 0; fib[1] = 1; for (int i = 2; i 바텀업 dp로 풀었다. (AC) 피보나치 수 2 (백준 2748번)https://www.acmicpc.net/..

https://www.acmicpc.net/problem/2755 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int cnt = 0; double sums = 0; while (n--) { string name, grade; int weight; double score = 0; cin >> name >> weight >> grade; if (grade == "A+") score = 4.3; else if (grade..