문제링크 : 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..
문제링크 : https://www.acmicpc.net/problem/13241#include using namespace std;typedef long long ll;ll A, B;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> A >> B; cout 간단한 최소공배수 구하는 문제이다.다만 최소공배수의 값이 커지는 것을 대비해 자료형을 int가 아닌 long long int를 사용하는 것에만 주의하면 된다.
문제링크 : https://www.acmicpc.net/problem/24313#include using namespace std;typedef long long ll;int a1, a0, c, n0;int arr[101];int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> a1 >> a0 >> c >> n0; int tmp1 = a1*n0+a0; int tmp2 = c * n0; if (a1 > c) cout 문제에 주어진 조건을 그대로 따라하면 된다.다만 주의할점으로 a1이 c보다 큰지 체크해야한다.만약 a1 > c라면 어떤 n에서도 c * n이 a1 * n + a0보다 클 수 없기 때문에 0을 ..
문제링크 : https://www.acmicpc.net/problem/9613#include using namespace std;typedef long long ll;int T, N;int arr[101];int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> T; while(T--) { cin >> N; long long result = 0; for(int i=0; i> arr[i]; for(int i=0; i 주어진 값에 대한 최대공약수를 구하고, 이러한 모든 최대공약수 합을 구하는 문제이다.입력받은 값을 배열로 저장하고, 현재 값 기준 나머지 값들과의 최대..
문제링크 : http://acmicpc.net/problem/2485#include using namespace std;typedef long long ll;int N;int arr[100001];vectorv;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; for(int i=0; i> arr[i]; for(int i=0; i 최대공약수를 활용한 문제이다.각 거리의 간격을 살펴보면 다음과 같다.1 3 7 13간격 : 2, 4, 6 (필요 0개, 1개, 2개) 각 간격의 최대 공약수를 구하면 2다.필요 갯수를 살펴보면 해당 간격/최대공약수 - 1을 하면 각 간격의 필요 개수인 것을 알 수 있다.
문제링크 : https://www.acmicpc.net/problem/1735#include using namespace std;typedef long long ll;int A1, B1, A2, B2;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> A1 >> A2 >> B1 >> B2; int a = A1*B2 + B1*A2; int b = A2*B2; int tmp = gcd(a,b); cout 주어진 값에 따라 공통분모와 그에 대한 분수를 구해준다.기약 분수를 구해야하기 때문에 구한 분모와 분수에 대해 최대공약수를 GCD를 통해 구해주고,분모와 분수에 각각 나눠주면 된다.
문제링크 : https://www.acmicpc.net/problem/1011#include using namespace std;typedef long long ll;int T;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> T; while(T--) { ll x, y; cin >> x >> y; ll gap = y-x; double n = sqrt(gap); int n2 = round(sqrt(gap)); if(n 먼저 거리에 따른 규칙을 찾아봐야 한다.거리 형태 횟수1 1 12 11 23 111..