[백준 - 17509] And the Winner Is... Ourselves!

||문제 이해

각 문제들의 최소 패널티 총합을 구하는 문제

 

각 문제는 D(풀이 시간), V(오답판정 개수) 가 있다.

풀이 시간 : 시간은 누적된다!

각 문제의 패널티는 D + (20 * V) 로 구해진다.

---

||해결 계획

처음은 마땅히 좋은 방법이 생각안나서 시간이 작은것 부터 해볼까라는 생각으로 무작정 시작했다.

이 처럼 같은 전략의 반복은 Greedy가 어울려 Greedy를 사용한다.

---

||계획 검증

두가지 경우가 있다.

시간의 비교, 오답판정의 비교

어떤 경우를 먼저 해야 하는지 검증해본다.

시간의 비교

두개의 문제가 있다 생각한다.

1번 : D = 10, V = 1

2번 : D = 20, V = 1

 

시간이 작은것부터 할 경우

1. 10 + 20 = 30

2. 30 + 20 = 50

= 30 + 50 = 80

 

시간이 큰것부터 할 경우

1. 20 + 20 = 40

2. 30 + 20 = 50

= 40 + 50 = 90

 

즉, 시간은 작은것부터 해야 최소가 나온다.

오답판정의 비교

두개의 문제가 있다 생각한다.

1번 : D = 10, V = 1

2번 : D = 10, V = 2

 

오답판정이 작은것부터 할 경우

1. 10 + 20 = 30

2. 20 + 40 = 60

= 30 + 60 = 90

 

오답판정이 큰것부터 할 경우

1. 10 + 40 = 50

2. 20 + 20 = 40

= 50 + 40 = 90

 

즉, 오답 판정은 상관 없다.

 

그럼 시간을 오름차순으로 정렬만 해주고 계산해주면 정답이 나온다.

---

||구현

#include <bits/stdc++.h>
using namespace std;
#define MAX 11

typedef pair<int, int> pii;
#define Time first
#define Verdict second

//시간을 오름차순으로 정렬
bool comp(const pii & a, const pii & b)
{
	return a.Time < b.Time;
}

pii p[MAX];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	for (int i = 0; i < MAX; ++i)
	{
		cin >> p[i].Time >> p[i].Verdict;
	}
	sort(p, p + MAX, comp);

	int result = 0;
	int time = 0;
	for (auto data : p)
	{
		time += data.Time;
		result += time + (data.Verdict * 20);
	}

	cout << result;
	return 0;
}

---

||되돌아 보기

일단 숨겨진 조건을 찾기 어려웠다ㅠ (영어라 내가 해석을 잘 못해서 그런걸 수도 있다...)

그 조건은 시간이 누적된다는 점이다.

 

처음에는 어 그냥 각 문제마다 D + 20 * V 하면 되는거 아니야? 하고 테스트 케이스를 보고 비교했지만

어림도 없었다.

 

그러다 생각나게 시험이니까 시간이 누적된 시간으로 계산 하는 것인가? 하고 테스트케이스와 비교해서 알아냈다.

영어도 공부 많이 해야겠다..ㅜ