0과 1의 쉼터

문제 캠프 내내 그랬듯이, 여전히 옆 나라와의 전쟁이 한창이다. 전쟁에는 N개의 부대가 투입되었는데, 전쟁이 장기전이 되다 보니 군사의 적절한 배치를 위해 각 부대에 군인이 늘어나기도 하고 줄어들기도 하고 있다. 행정의 편의를 위해 각 군인들에겐 번호가 붙어 있는데, 군인들은 1번 부대부터 군번순서대로 차례차례 배치된다. 예를 들어 1번 부대에 4명, 2번 부대에 3명, 3번 부대에 7명의 군인이 있다면 군번이 6번인 군인은 2번 부대에 배치되게 된다. 문제는 어떤 부대의 인원이 늘어나거나 줄어들었을 때 i번 군인이 어디에 배치되는지 인데, 이럴 때에는 군인도 군번도 처음부터 다시 배치하게 된다. 위의 예에서와 같이 1번 부대에 4명, 2번 부대에 3명, 3번 부대에 7명의 군인이 있었는데, 1번 부대에..

풀이 출발지(from)와 목적지(to)에 대해 연결된 다리 중 최대중량을 구하는 문제다. 입력받은 다리의 중량제한에 대해 내림차순 정렬 후 순서대로 union시키며, from과 to가 동일한 집합에 속하는지(연결됬는지) 확인해주어 연결된 순간 union한 간선의 가중치가 최대 가중치이므로 출력하면 된다. 소스코드 소스코드 보기 출처 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net

풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"와 푸는 방식이 동일한 문제이다. 소스코드 #include int dp[1000001] = {1000001}; int main(){ int N; scanf("%d", &N); int val, back = 0; for(int i = 0; i dp[back]) dp[++back] = val; else{ int left = 0, right = back, mid, idx; while(left = val) right = (idx = mid) -1; else left = mid + 1; } dp[idx] = val; } } printf("%d", back + 1); } 출처 및 참고자료 2..

풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"와 동일하지만, 입력받는 숫자들의 범위가 더 크다. 기존 코드로 풀린다. 소스코드 #include int dp[1000001] = {1000001}; int main(){ int N; scanf("%d", &N); int val, back = 0; for(int i = 0; i dp[back]) dp[++back] = val; else{ int left = 0, right = back, mid, idx; while(left = val) right = (idx = mid) -1; else left = mid + 1; } dp[idx] = val; } } printf("%d", ba..

풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"에서 부분 수열의 최대 길이를 lower bound방식으로 빠르게 구했지만, 이렇게 만들어진 임의의 수열들의 요소가 최대 길이를 이루는 요소들이 아님을 예시를 통해 알 수 있었다. 한마디 더 붙이자면, 임시로 생성하는 수열의 최댓값보다 작은 경우에는 lower bound으로 찾은 index위치에 덮어쓰기 때문에 최대 길이를 이루는 요소가 아님을 알 수 있다. 만약 입력받은 요소들이 몇 번째 index에서 덮어쓰기가 되는지 알 수 있다면, 이전의 방법으로 구한 부분 수열의 최대 길이와, 입력받은 요소의 개수 N을 조건에 따라 줄여가면, 요소들을 구할 수 있다. 소스코드 #include #define MAX 1000001 int arr[MAX], te..

풀이 "백준 11053, 가장 긴 증가하는 부분 수열"보다 수열의 크기가 커, 기존의 방법대로 하면 시간초과가 발생한다. 수열 전체에서 binary search로 특정한 조건의 부분 수열을 탐색하는 방법은 아닌 것 같아 lower bound만을 이용했다. 다음과 같이 수열의 길이만을 계산하기 위해 다음과 같이 수열을 만들었다. i = 0이거나, 생성 중인 수열의 가장 뒷 값보다 큰 경우에는 길이를 늘려준다. 위의 조건이 아닐 때마다, lower bound로 적절한 위치에 입력받은 값을 삽입한다. 10 20 10 11 20 와 같은 수열을 입력 받았다고 가정하자. 앞에서 순차적으로 값이 커지는 경우만 계산을 한다면 10 20으로 최대 길이가 2다. 때문에, 11처럼 20보다는 작지만, 10보다는 큰 경우 ..

풀이 A와 B의 부 배열에 대한 누적 합을 계산 후 정렬해주고, upper/lower bound로 가능한 경우를 계산해주면 된다. 단, 가능한 경우가 없을 수 있으니 left = diff) right = mid - 1; else left = mid + 1; mid = (left+right) / 2; }while (left

풀이 "백준 2470, 두 용액"의 응용 문제이다. 세 개의 특성값을 비교해야 하므로, 맨 왼쪽부터 기준이 되는 idx번째 특성값과, idx+1 ~ N-1의 특성값을 더해 0에 가장 가까운 용액을 만들어내는 특성값을 찾으면 된다. 단, 세 개 특성값의 최댓/최솟값이 int 범위를 벗어나므로, llabs()를 사용하고, 연산의 범위를 long long으로 선언했다. 소스코드 #include #include #define ll long long 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++) ..

풀이 "백준 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..

풀이 특성값의 합이 기존에 구한 특성값의 합보다 작다고 항상 0에 가까운건 아니다. ex) -1 + 1 = 0, -10 + 1 = -9 때문에 특성값 합의 절대값을 이용해 구해야한다. 새로운 특성값 합의 절대값이 기존 특성값 합의 절대값보다 작을 때, 새로운 특성값의 합과, 두 용액의 특성값 또한 새로 담아주어야 한다. 소스코드 #include #include int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); int left = 0, right = N-1, sum = 2e9; int left_val = arr[left], right_val = arr[right]; while (le..