시나브로

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

차고 같은 경우, 무조건 작은 인덱스 차고부터 써야되니 자료형 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 ..