Memo
•
g++ 은 똑똑해서 algorithm 헤더를 추가하지 않아도 sort()함수를 알아서 찾아준다...???
•
처음엔 dp배열을 만들어서 memorization을 해줘야 하나 고민했었다.
입력이 아래와 같이 들어온다. 우리는 모든 사람이 기다리는 시간의 최소값을 구해야한다.
5
3 1 4 3 2
Shell
복사
반복문을 돌려서 모두 더하는 방법
가장 쉽게 생각할 수 있는 해결법은 들어온 배열을 오름차순으로 정렬한 뒤 루프를 돌면서 처음부터 해당 위치의 값을 더하면 된다. 이 경우에는 아래와 같이 생각할 수 있다.
sorting 후
-> 1 2 3 3 4
Loop
1 : 1
2 : 1 + 2
3 : 1 + 2 + 3
4 : 1 + 2 + 3 + 3
5 : 1 + 2 + 3 + 3 + 4
다 더하면 32
Shell
복사
나오는 기준으로 곱해서 계산하기
sorting 후
-> 1 2 3 3 4
아래처럼 계산해야 하므로
1 : 1
2 : 1 + 2
3 : 1 + 2 + 3
4 : 1 + 2 + 3 + 3
5 : 1 + 2 + 3 + 3 + 4
5번 |4번 |3번 |2번 |1번
이 반복문을 곱셈식으로 바꾸면
result = (1 * 5) + (2 * 4) + (3 * 3) + (3 * 2) + (4 * 1);
Shell
복사
Code
제출 날짜
@4/1/2021
메모리
2016 KB
시간
0 ms
#include <iostream>
#include <vector>
#include <algorithm>
int N;
int result;
std::vector<int> arr;
void output()
{
std::cout << result;
}
void solution()
{
std::sort(arr.begin(), arr.end());
for(int i = N ; i > 0 ; --i)
result += arr[N - i] * i;
}
void input()
{
std::cin >> N;
arr.resize(N);
for (int i = 0 ; i < N ; ++i)
std::cin >> arr[i];
}
void preset()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
preset();
input();
solution();
output();
}
C++
복사
