[Atcoder] AtCoder Beginner Contest 401 후기

서론

그럭저럭 만족할만한 성과를 거둔 컨테스트였습니다.

Problem

A

if 문 하나로 풀리는 문제입니다.

B

$n$개의 Query에 대해, state machine 설계를 하면 되는 문제였습니다.

C

구간 합과 modulo 연산을 이용해서 $O(n)$시간 안에 Bottom-up 방식으로 재귀적으로 계산하면 됩니다.

D

문자열 $s$와 길이 $n$, 사용할 수 있는 o의 개수 $k$가 주어졌을 때, 모든 o을 이웃시키지 않는 문자열을 만드는 문제입니다.

이때, 문자열의 어떤 문자 ? 의 후보가 o나 .가 될 수 있으면, ?로 표시하고, 후보가 하나라면, 그것에 맞게 변환해주면 됩니다.

o의 근처에 있는 문자들을 전부 .로 치환하고 나면, ??? 같은 문자열들이 나오는데,

이 문자열에 들어갈 수 있는 o의 개수가 정확히 $k$개라면, ?의 개수가 홀수개인 경우에 한해 o.o 형태로 잘 바꾸는.. 문제입니다.

ex) ????? -> o.o.o

D번을 푸는 알고리즘 구상은 빠르게 했지만, 첫 문자열 $s$에서 o의 개수를 제외한 $k’$가 $0$일때 ?를 전부 .으로 치환해야 하는 것을 빼먹었던 것 말고는 할만했던 문제입니다.

정리

E와 F는 아직 지식도 부족한 것 같고, 중간고사 시즌이라 리뷰는 넘어갑니다..!