정화 코딩

https://www.acmicpc.net/problem/1214 대충 이런식으로 써가면서 답을 어떤식으로 구해야 할지 생각해봤다. 일단 p d에서 q의 배수(tq)를 뺀 값(dif)을 p로 나누어서 나머지(rem)를 구했다. 이 때 나머지가 음수거나 0이면 p를 더해서 0보다 큰 값으로 바꾸어준다. 이 값이 가장 큰 경우에 지불할 수 있는 금액의 최소가 된다. 그래서 아까 구한 나머지(rem)가 가장 클 때 답을 구하면 되는데, d에서 뺐던 그 q의 배수(tq)에 몫(quo)을 더해주면 된다. 몫(quo)은 아까 나머지에 p를 더하는 과정을 거쳤으면 그냥 몫으로 계산하면 되고, 그렇지 않았다면 몫+1로 계산하면 된다. 아 그리고 아까 구한 나머지(rem)가 0일 때는 거스름돈 없이 딱 맞게 돈을 지..

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/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의 범위가 그렇게 ..

3회차 - n log n 정렬, 기초 수학   수 정렬하기 2 https://www.acmicpc.net/problem/2751C++ STL에 있는 정렬 함수를 사용한 풀이입니다. 정렬 함수를 사용하기 위해 헤더를 포함시켰습니다.#include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(n); for (int i = 0; i > a[i]; sort(a.begin(), a.end()); for (int i = 0; i   수 정렬하기 3https://www.acm..

https://www.acmicpc.net/problem/19699 #include #include #include #include using namespace std;bool p[10000];int n, m;vector h;vector chk;set ans;void dfs(int idx, int res) { if (idx == m) { if (res > n >> m; h = vector(n); chk = vector(n, false); for (int i = 0; i > h[i]; sort(h.begin(), h.end()); dfs(0, 0); if (ans.empty()) { cout 우선 에라토스테네스 체로 1부터 10000까지 범위에..

https://www.acmicpc.net/problem/25333 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int a, b, x; cin >> a >> b >> x; vector chk(x + 1, false); queue q; q.push(0); chk[0] = true; int cnt = 0; while (!q.empty()) { i..

https://www.acmicpc.net/problem/17433 #include #include using namespace std;int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x % y);}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t, n; cin >> t; while (t--) { cin >> n; vector num(n); vector dif(n - 1); bool inf = true; for (int i = 0; i > num[i]; ..

https://www.acmicpc.net/problem/1684 #include #include #include using namespace std;int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x % y);}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector num(n); vector dif(n - 1); for (int i = 0; i > num[i]; if (i == 0) continue; dif[i - 1] = abs(num[i] - num[i -..