[Atcoder] AtCoder Beginner Contest 397 후기

서론

이번에도 A,B,C는 수월하게 풀었지만, D~부터는 역시 벽을 느낀 콘테스트였습니다.

Problem

A

단순히 if문 분기처리를 하는 문제였습니다.

B

문자열이 주어지면 ioioio… 형태로 만들기 위해 해야하는 최소한의 동작을 구하는 문제인데,

상태를 잘 정의하면 반복문 하나로 풀 수 있는 문제였습니다.

C

배열을 둘로 나눴을 때 각 배열에서 구분되는 숫자의 개수를 최대화하는 문제였습니다.

이 문제 또한 for문을 진행하면서 max값을 구할 수 있습니다.

D

어떤 정수 $N$(long long 범위)가 주어지면, $y^3 - y^3 = N$을 만족하는 $x$와 $y$를 아무거나 찾는 문제였습니다.

정석적인 풀이는 $x^3 - y^3 = (x-y)(x^2 + xy + y^2)$를 잘 변형해서 푸는 겁니다.

여기서 핵심적인 아이디어는 $d = x - y$를 정의하는 겁니다.

그러면 $N$의 약수를 $d$라고 치고 약수에 대해 브루트포스 및 이분탐색을 하면 풀리는 문제인데.

오버플로우에 대해 해결을 못하기도 했고, 무엇보다 이분 탐색을, 구현은 쉽게 하는데 정밀하게는 구현을 못해서,, 아쉬웠던 문제입니다.

번외로 투 포인터를 이용한 브루트-포스 방식으로도 문제가 풀려서 신기했습니다. 딱 시간제한에 걸린 코드..

E

주어진 트리의 정점들을 $N×K$ 행렬 형태로 분할하여, 각 행이 길이 $K$인 경로를 이루고 모든 정점이 정확히 한 번씩 등장하도록 할 수 있는지 판별하는 것이라고는 합니다.

(문제 구상도 안해봤습니다.)

F

C문제를 2개로 쪼개는게 아닌 3개로 쪼개는 문제입니다.

시간복잡도가 $O(n^2)$이 나오면 안되서, 뭔가 세그먼트 트리같은걸 써서 풀어야 한다는 아이디어만 도달한 문제였습니다.

에디토리얼에서는 DP와 lazy-SegmentTree를 이용해서 구현하는 문제였습니다.

lazy-SegmentTree? 도 한번 공부해볼 예정입니다.

G

최소 컷 문제로 바꿔 푸는 건데, 아직은 이걸 풀기에는 가야할 길이 너무 멉니다..

정리

D번 문제에 대해 오버플로우를 해결만 했다면 풀었을 텐데.. 아쉬움이 남습니다.