Educational Codeforces Round #122

늦었지만 올리는 후기

A. Div. 7

어떤 수 n 이 주어졌을 때, 숫자를 최소한으로 바꾸어 7으로 나뉘는 수를 구하는 문제.
바뀐 숫자는 0으로 시작하면 안된다.

n과 자리수가 같은 7으로 나누어지는 수를 iteration하며 숫자가 다른 횟수를 센 후, 횟수가 가장 작은 수를 구하였다.

어차피 n이 최대 999라 brute force로도 충분했다.

B. Minority

0과 1으로만 구성된 string이 주어졌을 때, substring의 minority의 최대 갯수를 구하는 문제.

여기서 minority란 substring 안에서 1의 갯수가 0보다 더 많으면 0, 0이 더 많으면 1이다.

갯수가 같은 경우 minority는 없다.


가장 큰 substring은 결국에 string 그 자체이다.

그래서 string의 1과 0 갯수를 센 뒤 수가 더 작은 것을 출력하였다.

만약 같은 경우 string의 첫번째 원소를 뺀 string을 생각해 주었다. (무조건 갯수가 다르게 나올수 밖에 없다)

C. Kill the Monster

캐릭터와 몬스터의 체력과 공격력이 주어졌을 때, 캐릭터를 k번 강화시켜 몬스터와의 전투에서 이길수 있는지를 판별하는 문제.

k가 2×10^5로 넉넉하여 1부터 순회하며 판별식을 써먹었다.

D. Make Them Equal

결국 knapsack 문제라는 것은 쉽게 판단이 섰다. 하지만 제한시간 내에 10^9만큼 순회를 못하지 않냐라는 생각때문에 계속 해매다가 못풀었다.

답을 찾아보니 아주 단순했는데, 순회를 하며 체크할 index의 상한선을 조절해주는 것이었다.

관련 문제를 풀 때 유용한 최적화를 배우게 되었다.