[백준 2470] 두 용액 [C]
풀이 "백준 2467, 용액"과 동일한 문제이다. 단, 입력되는 특성값이 항상 오름차순이라는 문구가 빠졌다. 정렬 후 탐색을 해주자. 소스코드 #include #include #include int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); qsort(arr, N, sizeof(int), compare); int left = 0, right = N-1, sum = 2e9; int left_val = arr[left], right_val = arr[rig..
2021. 8. 26.
[백준 1806] 부분합 [C]
풀이 연속된 수들의 부분합이기 때문에 Two Pointers로 쉽게 구현할 수 있다. start, end가 가르키는 배열의 합들이 S이상이면 최소 길이를 구해야 하며, 만약 sum이 S보다 작으면 end+1번째 요소를 더해주고, 그렇지 않다면 start번째 요소를 빼주는 방식으로 풀이했다. 소스코드 #include #define min(a, b) a < b ? a : b int main(){ int arr[100000], N, S, start = 0, end = 0; scanf("%d %d %d", &N, &S, &arr[0]); for (int i = 1; i < N; i++) scanf("%d", &arr[i]); int cnt = 1e5, sum = arr[0]; while (start = S) c..
2021. 8. 25.
[백준 7453] 합이 0인 네 정수 [C]
풀이 제한시간이 12초이기 때문에 모든 쌍을 확인하면 시간초과가 발생한다. 때문에, A~B, C~D의 합을 저장하고, Binary Search을 사용해 풀이했다. 합이 0인 쌍의 개수를 모두 구해야 하므로, 다음과 같이 upper/lower bound를 구현했다. qsort(AB, N, sizeof(int), compare); qsort(CD, N, sizeof(int), compare); long long cnt = 0; for (int i = 0; i 0) right = mid; else left = mid ..
2021. 8. 16.
