집합과정 프리랜서

자유직업인 인테리어 업자 두 요청 일정 겹치게 됨. 일정 모두 소화할 수 없음 겹치지 않는 요청들로 일정을 구성해야 함 이런 가능한 일정 중, 가장 돈을 많이 벌 때의 금액을 구하는 프로그램을 작성

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #define MAXN 500 #define MAXM 10000 #define MAX(a,b) (a)>(b)?(a):(b) int N, M; typedef struct { int s; int e; int c; } DATA; DATA data[MAXM + 1]; int d[MAXM + 1]; void input(); void DP(); void SWAP(DATA *a, DATA *b) { int tmp = a->s; a->s = b->s; b->s = tmp; tmp = a->e; a->e = b->e; b->e = tmp; tmp = a->c; a->c = b->c; b->c = tmp; } void quickSort(int first, int last) { int pivot; int i; int j; if (first < last) { pivot = first; i = first; j = last; while (i < j) { while (data[i].e <= data[pivot].e && i < last) { i++; } while (data[j].e > data[pivot].e) { j--; } if (i < j) { SWAP(&data[i], &data[j]); } } SWAP(&data[pivot], &data[j]); quickSort(first, j - 1); quickSort(j + 1, last); } } int binarySearch(int low, int high, int target) { int mid; if (low > high) { return 0; } mid = (low + high) / 2; if (target < data[mid].e) { binarySearch(low, mid - 1, target); } else if (data[mid].e < target) { if (data[mid + 1].e > target) return mid; else binarySearch(mid + 1, high, target); } else { return mid; } } int main(void) { int test_case; int T; freopen("test.txt", "r", stdin); setbuf(stdout, NULL); scanf("%d", &T); for (test_case = 1; test_case <= T; ++test_case) { input(); quickSort(1, N); DP(); printf("#%d %d\n", test_case, d[N]); } return 0; //정상종료시 반드시 0을 리턴해야 합니다. } void input() { scanf("%d %d", &N, &M); for (int i = 1; i <= N; i++) { scanf("%d %d %d", &data[i].s, &data[i].e, &data[i].c); } } void DP() { for (int i = 1; i <= N; i++) { if (i == 1) d[i] = data[i].c; else { d[i] = MAX(d[i - 1], d[binarySearch(1, i - 1, data[i].s - 1)] + data[i].c); } } }

- 왜 정렬을 하고 풀이 하지 - 단순하게 풀면 안되나 - 아 입력이 들어올 때가 다른 것인가 - 그리고 디피로 풀이하는 것은 동일함