Search
Duplicate
🍋

ATM

주차
14
문제번호
11399
언어
C++
티어
실버
유형
그리디
nj_Blog
nj_상태
이해도
풀이
풀이 O
사람
이해도 2
13 more properties

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++
복사