Codeforces Round #493 (Div. 2)

A - Balloons

서로 packet을 나누어 가질 때 하나 이상의 packet을 가지며 packet에 들어있는 풍선의 수는 같지 않게 해야할 때

어떤 packet의 인덱스를 가져갔는 지 출력하는 문제이다.

N이 1일 때에는 무조건 한 명은 packet을 받지 못하니 불가능하고

packet에 있는 풍선의 수들을 정렬한다면 가장 적은 수의 풍선이 든 packet은 N이 2일 때를 제외하고는

나머지 packet들의 풍선을 더했을 때보다 무조건 적다는 것을 알 수 있다.

그러므로 N이 1 또는 N이 2이며 두 packet에 들어있는 풍선의 개수가 같은 경우는 -1,

아닌 경우에는 풍선이 가장 적은 packet을 제외한 packet의 인덱스 번호를 출력해주면 된다.

인덱스 번호를 출력해야함을 조심하자

B - Cutting

홀수의 수와 짝수의 수가 동일하게 연속된 구간을 나눌 때 B원이하로 이들을 자르는 횟수의 최댓값을 구하는 문제이다.

이미 홀수의 수와 짝수의 수가 동일한 그룹의 경우 이들을 자르지 않고 합쳐도 홀수의 수와 짝수의 수는 동일하기 때문에 

나누는 구간은 정해져 있다는 것을 알 수 있다.

앞에서부터 홀수의 수와 짝수의 수가 같아지는 구간과 그 구간을 자르는 비용을 저장한 뒤

탐욕법을 이용하여 이들을 정렬하여 작은 비용부터 구매할 수 있을 때까지 구매하여 그 개수를 출력하면 되는 문제이다.

 

C - Convert to Ones

뒤집는 것의 비용이 X, 반전 시키는 것의 비용이 Y일 때 이 문자열을 모두 1로 만드는 데의 최대 비용을 구하는 문제이다.

(0*)(1*)(0*)(1*)...과 같은 문자열에서 반전 시키는 횟수의 최솟값은 0만으로 이루어진 연속된 문자열의 개수가 된다.

구간을 뒤집을 경우 구간을 반전 시키는 개수가 줄어들 수 있는데

이 때 0만으로 이루어진 연속된 문자열의 개수는 최대 1개씩 줄어든다.

즉 다시 말해 구간을 한번 더 뒤집을 때마다 최대 구간을 한번 덜 반전시킬 수 있으며

이 횟수들의 합은 정해져 있으므로 모든 경우의 수에 X, Y값을 각각 곱하여 이들의 최솟값을 구해주면 된다.

즉, 전체 0만으로 이루어진 연속된 문자열의 개수를 cnt라 할 때 cnt값이 0일 경우는 모두 1인 문자열이므로 0을 출력하고,

아닐 경우에는 cnt*X+(cnt-i)*Y (i는0~cnt-1) 값의 최솟값을 구하여 문제를 풀 수 있다.

D - Roman Digits

1, 5, 10, 50을 뜻하는 I, V, X, L를 N개를 사용하여 합했을 때 나타낼 수 있는 수의 개수를 묻는 문제이다.

풀이가 이해가 가지않아 며칠동안 고민을 해보았는데 제대로 이해가 되지 않았다.

그냥 규칙을 찾는 문제로 접근을 해야하는 건지.. 아직 원리를 깨닫지 못한 문제이다.

E - Sky Full of Stars

X