[Atcoder] AtCoder Beginner Contest 396 후기

서론

이 컨테스트에서도 c++의 STL 정리가 매우 중요하다는 것을 깨달았던 콘테스트였습니다.

Problem

A

배열의 원소들중 연속되는 3개의 값이 존재하는지 여부를 묻는 문제였습니다.

반복문 하나로 간단히 풀었습니다.

B

스택을 푸시, 팝하면서 쿼리를 진행하는 문제입니다.

이것도 간단히 풀었습니다.

C

어떤 그룹 A와 그룹 B의 원소들이 특정 값을 가지고 있고,

원소들을 마음대로 뽑을 수 있으나, 그룹 B보다 그룹 A를 같거나 더 많이 뽑아야 하는 문제입니다.

사실 이 문제를 보자마자, 그룹 A와 B의 원소들을 내림차순 정렬해서 부분 합을 이용해서 푸는 아이디어에는 빠르게 도달했습니다만..

놓친 부분들이 몇 개 있었습니다.

1. 내림차순을 도와주는 함수는 sort(vec.begin(), vec.end(), greater<long long>());입니다.
2. 또한 lower_bound(vec.begin(), vec.end(), 0, greater<long long>());을 사용할 때, 만약 0보다 큰 값이 존재하지 않아도 vec.begin()을 리턴한다는 점입니다.
3. greater<>() 같은 것을 쓸 시에 형이 long long인지 int인지 잘 확인해야 합니다.

구현에서 소중한 시간을 다 잡아먹어버렸다..

D

그래프니까 DFS/BFS로 풀어야겠지라고 생각했다가 뭔가 비트필드를 이용한 DP문제인줄 알아서 풀다가.. 여러 방면으로 삽질을 했습니다.

그냥 DFS/BFS를 이용한 완전탐색 문제여서, 아쉬웠습니다.

정리

A~D가 생각보다 풀 만한 문제였음에도, c++에 익숙해지기까지는 아직도 시간이 걸리나 봅니다. 시간이 난다면 STL을 정리해야할 것 같습니다!