1) n개의 아이템을 정렬하는 시간 O(nlogn) * m번 수행 = O(mnlogn)
n(1 <= n <= 100) 아이템의 개수 , m(1 <= n <= 1만) 아이템 사용 횟수 이기 때문에 O(mnlogn)은 O(100 * 100 * 10) = O(10만) 문제의 시간 제한이 10초 이기 때문에 시간이 남아돕니다.
#include <iostream>
#include <algorithm>
#define max_int 101
using namespace std;
//시간 복잡도: O(mnlogn)
//공간 복잡도: O(n)
//사용한 알고리즘: 그리디, STL sort
//사용한 자료구조: 배열
int t, n, m, result;
// 아이템 정보를 담는 배열
int a[max_int];
int main(){
scanf("%d", &t);
for(int test_case = 1; test_case <=t; test_case++){
// 1. 변수 초기화
result = 0;
// 2. 정보를 입력받는다.
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
}
// 3. m번 만큼 아이템을 사용합니다.
while(m--){
// 마력 내림차순으로 정렬
sort(a, a+n, greater<int>());
// 제일 마력이 많이 들어있는 아이템을 사용합니다.
result += a[0];
// 마력은 0이 되면 없어집니다.
if(a[0] > 0) a[0]--;
}
// 4. 결과 출력
printf("%d\n", result);
}
}
문제 - 0, 1, 2 ... n-1로 이름이 부여된 n마리의 거위가 있습니다. - k마리의 거위들이 탈출했습니다. - 탈출한 거위들의 이름의 합은 n으로 나누어 떨어집니다. - 탈출한 거위들의 집합이 총 몇 가지인지를 구하시오. -n(1 = n = 500) 전체 거위 수, k(1 = k = min(n, 100)) 탈출한 거위 수 - 시간 제한 3초 - 문...
오늘 한 일 - 삼각형 위의 최대 경로 수 세기, 마력 문제 풀고 정리 느낀점 -무계획 오늘 vue.js 강의 듣기로 했는데, 퇴근할 때 쯤 컨디션이 너무 않좋았다. 공부 안하려다가 오기는 왔는데, 강의가 듣고싶지가 않았다. 들으면 잘것 같았다. 그래서 계획을 어기고 알고리즘 풀었다. 사실 저것 말고도 몇개 더 풀었는데 너무 쉬워서 정리하지는 않았다...
문제 - 마력이 담긴 아이템이 n개 주어집니다. - 아이템을 사용하면 마력이 1씩 줄어들면서 0이 되면 아이템이 사라집니다. - 아이템을 m번 사용해서 얻을 수 있는 최대 마력의 양을 구하시오. -n(1 = n = 100) 아이템의 개수 , m(1 = n = 1만) 아이템 사용 횟수 - 시간 제한 10초 - 문제 링크 - 접근 과정 1. 그리디...
문제 - 사진과 같은 숫자 삼각형이 있습니다. - 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려갑니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. - 제일 아래 칸에서 얻을 수 있는 최대값의 경로 개수를 구하시오. (최대값은 여러개일 수 있습니다.) -C(C = 50) 테스트 케이스의 수 ,...
오늘 한 일 - 결혼식, BRAVE 문제 풀고 정리 - 고대어 사전 풀다가 실패 느낀점 -SHOW TO FINISH 예전에 스타트업에서 일할 때, 옆에 있는 팀의 대표님께서 SHOW TO FINISH 라는 말을 자주 사용하셨다. 그 의미는 완성하기 위해 보여준다. 최근에 코드를 작성하고, 블로그에 글...