-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
속도문제에 대해서 궁금한 것이 있습니다!
21.02.10 15:03 작성 조회수 85
0
46번 멀티테스킹을 C++로 풀어보았는데요, 채점 폴더에서 4번째 부터 타임리미트가 떠요 ㅠㅠ
그래서 궁금증이 생겼습니다.
deque을 사용하면 index를 사용해서 원소에 접근할 때 일반 배열보다 더 오래 걸리나요?
그게 아니라면, 어느 부분에서 더 느려져서 타임리미트가 뜨는 건가요?
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
#define endl '\n'
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, k, i, sum = 0;
cin >> n;
deque<int> arr(n);
for (i = 0; i < n; i++) {
cin >> arr[i];
sum += arr[i];
}
i = -1;
cin >> k;
if (sum <= k) {
cout << -1;
return 0;
}
while (k) {
i++;
if (i == n) i = 0;
if (arr[i] > 0) {
//cout << i << " ";
k -= 1;
arr[i]--;
}
}
while (1) {
i++;
if (i == n) i = 0;
if (arr[i] == 0) continue;
else break;
}
cout << i+1;
return 0;
}
답변을 작성해보세요.
1
답변 1