Codeforces Round #693 (Div. 3) 참가 후기

결론 : Rating은 또 떨어졌다... ㅠㅠ

 

Div 3는 Div 2보다는 문제가 쉬운 편이라 웬만하면 3문제는 푸는데..

 

이날은 2번째 문제에서 계속 막혀서 짜증 나서 끄고 잠..

(다음날 출근인데 너무 늦어서 그런 것도 있긴 함)

 

1번 문제는 비교적 빠르게 해결했는데

2번 문제가 나중에 보니 접근 자체를 조금 잘못했었다.

 

문제를 대략 요약하면

2명한테 사탕을 나눠줄 건데

사탕은 1g, 2g 두 가지 종류가 있으며 더 이상 분해가 불가능하다.

(1g을 0.5g 두 개로 나눈다던가, 2g을 1g 두 개로 나누는 등이 불가)

 

1g, 2g의 사탕이 여러 개 주어졌을 때

2명에게 균등하게 나눌 수 있으면 YES 출력, 못 나누면 NO 출력

 

나는 1g짜리 사탕의 개수를 구하고

2g짜리 사탕의 개수를 구해서

둘 다 짝수면 YES, 둘 중 하나라도 홀수면 NO를 출력하도록 코딩했다.

 

그런데 매우 간단한 반례가 있다.

5개의 사탕이 1g, 1g, 1g, 1g, 2g가 주어지면

1g * 3, 1g + 2g로 나눌 수 있으며

상기에 내가 작성한 알고리즘으로는 WA를 뱉어낸다.

 

이걸 어찌 풀지 고민하다가 잠들고

다음날 다른 사람이 푼 걸 보고 '왜 내가 이걸 생각 못했지?'라는 생각에 속상해졌다.

 

그 사람이 푼 알고리즘을 간단히 설명하면

총사탕의 g수의 합 나누기 2(n)

1g의 사탕 개수를 세고 (cnt1)

2g의 사태 개수를 센 뒤 (cnt2)

 

2중 for문을 이용해서

1g 사탕의 개수를 0에서 cnt1까지 

2g 사탕의 개수를 0에서 cnt2까지 순회하면서

1g 사탕의 개수 + 2g 사탕의 개수 * 2 == n이 되는 게 존재하면 YES

존재하지 않으면 NO를 출력하는 로직이었다.

 

Div 3라고 너무 방심한 것도 없지 않아 있었고

사실 별로 참여하고 싶지 않았던 마음도 있던 거 같다..

 

그다음 날 Div 2가 또 진행되었는데

어차피 안 풀릴 거 같아 패스했다.

 

이번 주 금요일은 좀 더 준비해서 문제 많이 풀어서 Rating 상승을 했으면 좋겠다.

다음날 출근은 안 하니까 시간 다 될 때까지 진행해봐야지..