문제링크 : https://www.acmicpc.net/problem/1456#include using namespace std;typedef long long ll;ll A, B;int main() { cin >> A >> B; vector v(10000001, true); v[0] = v[1] = false; for(int i=2; i*i= A) cnt++; //범위 내 카운트 if(tmp > B/i) break; //오버플로우 방지 tmp*=i; //거듭제곱 } } cout 에라스토테네스의 체를 활용한 문제이다.문제 범위에서 B가 최대 10^14이기에 이에 루트 값을 씌운 10^7범위까지 소수를 미리 체크해준다...
문제링크 : https://www.acmicpc.net/problem/2312#include using namespace std;int N, num;int main() { cin >> N; while(N--) { mapm; cin >> num; int tmp = num; for(int i=2; i*i 1) m[tmp]++; for(auto i : m) { cout 소인수 분해를 하고, 이때 소인수의 개수를 같이 출력하는 문제이다.반복문 i=2부터 시작하여 현재 입력받은 num을 나눌 수 있을 때까지 반복하여 나눠주며 map을 활용해 사용된 개수를 카운팅한다.이를 i*i주의할점은 마지막 소인수를..
문제링크 : https://www.acmicpc.net/problem/1064#include using namespace std;struct Point { double x, y;};double distance(Point a, Point b) //거리 구하기{ double dx = a.x - b.x; double dy = a.y - b.y; return sqrt(dx * dx + dy * dy);}bool isColinear(Point a, Point b, Point c) //세 점이 일직선에 있는 지 체크{ return (b.x - a.x)*(c.y - a.y) == (b.y - a.y)*(c.x - a.x);}int main() { Point a, b, c; ci..
문제링크 : https://www.acmicpc.net/problem/17087#include using namespace std;typedef long long ll;int N, S;int arr[100001];int main() { cin >> N >> S; vectorv; for(int i=0; i> arr[i]; v.push_back(abs(arr[i]-S)); } int tmp = abs(arr[0]-S); for(auto i : v) { tmp = gcd(tmp, i); } cout 최대공약수를 활용한 문제이다.입력받은 수빈이의 위치 S와 동생 간의 거리 차이 값을 모두 구하여 따로 저장하고,이 값들의 최대공약수를 구하..
문제링크 : https://www.acmicpc.net/problem/2089#include using namespace std;typedef long long ll;int N;int main() { cin >> N; if(N==0) { cout v; while(N!=0) { if(N%-2==0) { N/=-2; v.push_back(0); } else { N = (N-1)/-2; v.push_back(1); } } reverse(v.begin(), v.end()); for(auto i : v) c..
문제링크 : https://www.acmicpc.net/problem/1052#include using namespace std;typedef long long ll;int N, K;int main() { int N, K; cin >> N >> K; int add = 0; while (__builtin_popcount(N) > K) { N++; add++; } cout 먼저 1~10까지 직접 그려보며 규칙을 찾아보았다.21 1 -> 2 (10)31 1 1 -> 2, 1 (11)41 1 1 1 -> 2, 2 -> 4 (100)51 1 1 1 1 -> 2, 2, 1 -> 4, 1 (101)61 1 1 1 1 1 -> 2, 2, 2 -> 4, 2 (1..
문제링크 : https://www.acmicpc.net/problem/11576#include using namespace std;typedef long long ll;int A, B, m;int arr[26];int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> A >> B >> m; for(int i=0; i> arr[i]; int idx = 0, tmp = 0; for(int i=m-1; i>=0; i--) { tmp += arr[idx]*pow(A, i); idx++; } vectorv; while(tmp >= B) { v.push_..
문제링크 : https://www.acmicpc.net/problem/10973#include using namespace std;typedef long long ll;int N;int arr[10001];int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; for(int i=0; i> arr[i]; if(prev_permutation(arr, arr+N)) { for(int i=0; i [백준 10972번] 다음 순열 문제와 비슷한 유형이다.여기서는 next_permutation 함수대신 prev_permutation 함수를 통해 간단히 해결이 가능하다.
문제링크 : https://www.acmicpc.net/problem/1016#include using namespace std;typedef long long ll;ll n, m;int arr[1000001];int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(ll i=2; i*i 에라스토테네스의 채 방식을 응용하여 풀 수 있는 문제이다.먼저 입력 값 min과 max가 굉장히 큰 수이나, min~max 범위를 보면 100만으로 int 배열로 값을 저장할 수 있다. 따라서 최소 시작 값을 두고, 제곱 수를 곱해가며 시작 값 기준 해당 제곱 수의 배수들을 모두 체크해준다.반복문을 통해 최소 시..
문제링크 : https://www.acmicpc.net/problem/10986#include using namespace std;typedef long long ll;int N, M;ll arr[1000001], sum[1000001], cnt[1001];int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> M; for(int i=0; i> arr[i]; sum[0] = arr[0]%M; cnt[sum[0]]++; for(int i=1; i 단순 2중 for문으로 풀면 시간초과가 나는 문제이다.모듈러 연산을 통해 나머지가 같은 값들을 체크할 필요가 있다.입력값 1 2 3 1 2누적합 1 ..
문제링크 : https://www.acmicpc.net/problem/4134#include using namespace std;typedef long long ll;int T;ll N;bool cal(ll n) { if (n > T; while(T--) { cin >> N; while(!cal(N)) { N++; } cout 주어진 N보다 같거나 큰 소수를 찾는 문제이다.현재 N을 기준으로 소수 판별을 시작해 소수가 아니라면 계속 N 값을 증가시켜가며 다시 소수 판별을 해준다.주의할 점은 N의 범위가 매우 커서 long long으로 선언해주어야 한다는 점이다.소수 판별에서는 범위가 sqrt(n)이므로 l..
문제링크 : https://www.acmicpc.net/problem/10972#include using namespace std;typedef long long ll;int N;int arr[10001];int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; for(int i=0; i> arr[i]; if(next_permutation(arr, arr+N)) { for(int i=0; i next_permutation 함수를 통해 현재 배열에 대한 다음 조합이 있는 지 간단하게 체크가 가능하다.if문을 통해 있다면 배열 값을, 없다면 -1을 출력해준다.
문제링크 : https://www.acmicpc.net/problem/13909#include using namespace std;typedef long long ll;int N;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; cout 직접 경우의 수를 체크해보면 규칙이 보인다.n=3 -> 11 1 11 0 11 0 0n=4 -> 21 1 1 11 0 1 01 0 0 01 0 0 1n=5 -> 21 1 1 1 11 0 1 0 11 0 0 0 11 0 0 1 11 0 0 1 0n=6 -> 21 1 1 1 1 11 0 1 0 1 01 0 0 0 1 11 0 0 1 1 11 0 0 1 0 11 0 0 1 0..