꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/9020 백준 6588번 골드바흐의 추측(https://jaimemin.tistory.com/895)랑 유사한 문제였습니다.런타임 에러를 방지하기 위해 조건문을 넣는거랑 답이 여러개일 경우 두 수의 차가 제일 적은 조합을 출력하는 것만 유의한다면 쉽게 풀 수 있는 문제였습니다. #include #include #include using namespace std; const int MAX = 10000 + 1; const int INF = 987654321; int minFactor[MAX]; vector prime; void eratosthenes(void) { minFactor[0] = minFactor[1] = -1; for ..

문제 링크입니다: https://www.acmicpc.net/problem/2018 투 포인터 알고리즘을 적용해도 되고 등차수열 합을 이용해서 풀어도 되는 문제였습니다.저 같은 경우에는 등차수열 합을 이용해서 풀었습니다. $$x_1 + x_2 + x_3 + ... + x_k = (a+1) + (a+2) +(a+3) + ... + (a+k)=k*a + (k * (k+1))/2$$$$k*a+(k*(k+1))/2가\; N이\; 되기\; 위해서는\; k*a=N-(k*(k+1))/2이여야\;합니다.$$$$따라서,\;N-(k*(k+1))/2가\;k로 나누어\;떨어진다면\;해당\;수열의\;합은\;N입니다.$$ #include using namespace std; int main(void) { ios_base::syn..

문제 링크입니다: https://www.acmicpc.net/problem/14614 이산수학을 배웠다면 XOR의 특성을 알기 때문에 쉽게 풀 수 있는 문제였습니다. *C의 범위가 매우 크기 때문에 C를 string 형태로 입력받아야합니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int A, B; string C; cin >> A >> B >> C; if ((C[C.length()-1] - '0') % 2) cout

문제 링크입니다: https://www.acmicpc.net/problem/2143 N, M이 최대 1000이기 때문에 미리 시간복잡도 O(N^2)으로 모든 부분합을 전처리해주고 lower_bound, upper_bound를 이용하면 쉽게 풀 수 있는 문제였습니다. *답의 범위는 int 범위를 초과하므로 result는 long long이여야합니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); long long T; cin >> T; int N; cin >> N; vector A(N); for (int i = 0; i > A[i]; i..

문제 링크입니다: https://www.acmicpc.net/problem/2632 N과 M이 최대 1000이기 때문에 미리 시간복잡도 O(N^2)으로 전처리해도 무방한 문제였습니다. 알고리즘은 아래와 같습니다.1. 모든 가능한 합을 미리 v와 v2에 전처리 해줍니다.2. v[i]에 대해 lower_bound와 upper_bound를 이용하여 v2에 (pizza - v[i])가 몇개 있는지 확인하고 결과에 더해줍니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int pizza; cin >> pizza; int M, N; cin >> M >> N; vecto..

문제 링크입니다: https://www.acmicpc.net/problem/3020 lower_bound와 upper_bound를 적절히 이용하면 쉽게 풀 수 있는 문제였습니다.코드를 보면 금방 이해할 수 있을 것입니다. #include #include #include using namespace std; const int INF = 987654321; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, H; cin >> N >> H; vector bottom(N/2), top(N/2); for (int i = 0; i > bottom[i] >> top[i]; sort(bottom.begin(), bottom..

문제 링크입니다: https://www.acmicpc.net/problem/7453 완전탐색법을 적용하여 시간 복잡도 O(N^4)으로 풀려고 하면 절대 시간 안에 풀 수 없는 문제입니다. 알고리즘은 아래와 같습니다.1. 4개의 배열을 2개로 나눕니다. {첫 번째 배열, 두 번째 배열}, {세 번째 배열, 네 번째 배열}2. 첫 번째 배열과 두 번째 배열의 가능한 모든 합은 미리 전처리 할 필요 없고 세 번째 배열과 네 번째 배열의 모든 가능한 합만 미리 전처리해두고 오름차순으로 정렬합니다.3. 첫 번째 배열과 두 번째 배열의 모든 가능한 합을 구하고 해당 합의 부호를 바꾼 값을 갖고 있는 인덱스를 2번에서 구한 배열에서 찾아봅니다.4. 3번에서 구한 인덱스의 합과 2번에서 구한 합의 합이 0이라면 결과에..

문제 링크입니다: https://www.acmicpc.net/problem/1208 배열을 두개로 나누어서 모든 부분집합의 합을 비트마스킹을 이용하여 미리 전처리한 후 투 포인터 알고리즘을 적용해야했던 어려운 문제였습니다. 알고리즘은 아래와 같습니다.1. 배열을 두개로 나누고 각각의 배열에 대해 모든 부분집합의 합을 전처리해줍니다.2. 각각의 배열을 정렬을 하는데 하나는 오름차순 반대는 내림차순으로 정렬하여 투 포인터 알고리즘을 적용합니다.3. 배열을 두개로 나누었기 때문에 S=0일 경우 답이 하나 더 크게 나옵니다.-> 각 배열의 부분집합이 공집합을 포함하고 있기 때문입니다. 따라서, S=0일 경우 답을 하나 줄입니다. #include #include #include #include using name..

문제 링크입니다: https://www.acmicpc.net/problem/1644 에라토스테네스의 체와 투 포인터 알고리즘을 적용하면 쉽게 풀 수 있는 문제였습니다.에라토스테네스의 체를 적용할 때 i * i의 범위가 int 범위를 초과하므로 long long으로 반복문을 돌려야하는 것이 핵심이였습니다. #include #include #include using namespace std; const int MAX = 4000000; long long minFactor[MAX]; vector prime; //에라토스테네스의 체 void eratosthenes(void) { minFactor[0] = minFactor[1] = -1; for (long long i = 2; i < MAX; i++) minFa..

문제 링크입니다: https://www.acmicpc.net/problem/1806 백준 2003번 수들의 합 2(https://jaimemin.tistory.com/1104)와 같이 투 포인터 알고리즘을 적용하면 되는 문제였습니다. #include #include using namespace std; const int MAX = 100000; const int INF = 987654321; int arr[MAX]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, S; cin >> N >> S; for (int i = 0; i > arr[i]; int low = 0, high = 0; int sum = arr..