풀이 보관함
[C++] 백준 17509번: And the Winner Is... Ourselves! 본문
🔗 문제
17509번: And the Winner Is... Ourselves!
17509번: And the Winner Is... Ourselves!
11 lines are given as the input. The $i$-th line contains two space-separated integers, $D_i$ and $V_i$, where $D_i$ is the amount of minutes required to solve the $i$-th problem, and $V_i$ is the number of incorrect verdicts on the $i$-th problem. For eac
www.acmicpc.net
🖍 풀이
총 11 문제를 풀 것이다. 모든 문제를 풀 수 있는 문제들이며 각 문제마다 패널티가 부과된다.
문제 풀 때마다 패널티에 ‘총 소요 시간 + 20*틀린 횟수’를 추가된다.
✔️ 최적의 해 구하는 법
V는 D에 종속되지 않는다. 문제 풀이 시간이 적은 것부터 풀어야 패널티를 받는다.
1)
D: 10, V: 0
D: 20, V: 10
첫 문제에서 패널티는 10가 된다. 두 번째 문제에서 10 (첫 문제에서 추가된 10) + 10 + 20 (문제를 풀기 시작한 총 소요시간) + 10*20 = 240이 된다.
2)
D: 20, V: 10
D: 10, V: 0
첫 문제에서 패널티는 20 + 200 = 220가 된다. 두 번째 문제에서 220 + 20 + 10 + 0 = 250의 패널티로 더 많은 패널티가 부과된다.
💾 소스
#include <iostream>
#include <algorithm>
int main()
{
int D[11], V[11];
int time=0, result =0;
for(int i=0; i<11; ++i)
{
std::cin >> D[i] >> V[i];
}
std::sort(D, D+11);
for(int i =0;i<11;i++)
{
result += time + D[i];
time += D[i];
result += V[i]*20;
}
std::cout << result;
}