시나브로

처음 이 문제를 접했을 때, D2라는 수준을 감안하여 그냥 탐색해도 될까?라는 의문을 가지고 풀어 보았다. 운이 좋게도 이 솔류션으로도 해결이 가능했다. 하지만, 시간복잡도가 높기에 최적화를 해야될 것이다. Solution 최고값을 안다면, 그 값이 나오기 전까지 계속해서 구매한다면, 1만큼이라도 이익이 발생한다. 전체 값에서 최고값을 찾는다 최고값까지 모든 순간에 구매를 한다 최고값에 도착하면, 이후의 최고값을 다시 탐색한다 탐색한 결과값으로 최고값을 갱신하고 위의 과정을 배열이 끝날 때까지 반복한다 Key Point 입력을 보면 배열의 최고 길이는 1000000이고, 최대 매매가는 10000입니다. 이렇게만 보아도 int의 범위를 넘어갑니다. 그렇기에 sum(answer)의 자료형을 long long..

각 시점마다 오름차순인지 내림차순인지 확인해서 이전꺼와 다르다면 새로운 묶음으로 본다는 것에서 포인트를 얻어서 풀었다. #include #include #include #include using namespace std; int list[100010]; int signal = -1; void search_signal(int i) { if (list[i] list[i+1]) { signal = 2; } else { signal = 0; } } int main(void) { freopen("inp.inp", "r", stdin); freopen("out.out", "w", stdout); int tc = 0; cin >> ..

정렬을 한 이후, 최소값(start_point)과 m보다 작은 최댓값(end_point) 2개를 가지고 두개의 합이 m보다 클 경우, end_point를 옮겨서 두 개의 합을 줄이도록 하였다. 두개의 합이 m보다 작을 경우, start_point를 옮겨서 두개의 합을 크게하도록하엿다. #include #include #include using namespace std; int main(void) { freopen("inp.inp", "r", stdin); freopen("out.out", "w", stdout); int tc = 0; cin >> tc; for (int q = 0; q > n >> m; int start_point =..

차고 같은 경우, 무조건 작은 인덱스 차고부터 써야되니 자료형 vector를 이용해 역순으로 정렬해줘서 사용했다. 대기자 같은 경우, 큐 자료 구조를 이용하여 FIFO을 구현하였다. #include #include #include #include #include #include using namespace std; int car_box[101][2] = { 0 }; int car[2001][2] = { 0 }; queue stack; int price = 0; int n; int m; vector list; int fill(int index) { if (!list.empty()) { car[index][1] = list.back(); car_box[list.back()][1] = index; price ..