AtCoder Beginner Contest 439 후기

2026년 1월 4일에 진행한 AtCoder Beginner Contest 439에 참가했습니다. 2026년 첫 CP였는데, 3문제밖에 풀지 못했습니다. 그 결과 퍼포먼스 799, 레이팅 변화 -37로 처참하게 망해 버리고 말았습니다. 민트 컷에 머물러 있던 레이팅이 그린으로 복귀한 것은 덤이고요. 사실 이번 대회는 5솔을 해야 민트 퍼포가 나올 정도로 쉬운 대회였는데, 실력이 많이 떨어진 것 같습니다.

A. 2^n - 2*n (+1)

제출: 0분

제목만으로도 모든 것이 설명되는 문제입니다. 다만 ^이 Bitwise XOR는 아니고, 거듭제곱입니다.

B. Happy Number (+2)

제출: 2분, 10분

각 자리를 제곱하여 더하는 연산을 반복했을 때 $1$이 되는 수인지 묻는 문제입니다. 요구하는 대로 시뮬레이션 해주면 되는데, $N=1$인 경우를 잘못 처리하여 한 번 틀리고 두 번째 시도에 맞았습니다.

C. 2026 (-3)

제출: 8분, 17분, 40분

서로 다른 두 제곱수의 합으로 유일하게 표현 가능한 수를 묻는 문제인데, 앞선 B와 달리 $N$ 이하의 모든 가능한 수를 출력해야 합니다. 가장 쉽게 생각할 수 있는 것은 $x$와 $y$에 대한 브루트 포스입니다. $x$와 $y$를 각각 $\lceil\sqrt{N}\rceil$까지 반복시켜 시간 복잡도를 $O(N)$으로 만들었으나, 모두 TLE를 받았습니다. $N$이 상당히 커서 메모리를 줄이고자 map을 사용했는데, 이것이 시간을 많이 잡아먹은 것이 아닐까 추측해 봅니다.

D. Kadomatsu Subsequence (+1)

제출: 29분

수열에서 길이가 $3$이고 각 원소의 비가 $3:7:5$, $7:3:5$, $5:3:7$, $5:7:3$ 중 하나인 부분 수열의 개수를 구하는 문제입니다. C에서 2번의 TLE를 맞고 D를 고민하다가, $5$의 배수인 원소가 가장 오른쪽에 있는 케이스만 확인한다면 쉬운 문제가 될 것이라는 생각을 했습니다. 수열을 처음부터 보면서 해시맵에 $3$이나 $7$의 배수인 원소와 그 개수를 저장하고 있다가, $5$의 배수가 나오면 가능한 $3:7:5$ 또는 $7:3:5$의 개수를 확인해 주면 되죠. 이것을 역순으로 한 번 더 해주면 $5$의 배수가 가장 왼쪽에 있을 때도 볼 수 있고, 이것으로 AC를 받았습니다.

결과 및 업솔빙

그렇게 추가적인 문제를 풀지 못했고, 퍼포먼스 799의 참담한 성적을 받아들여야 했습니다. 업솔빙은 1월 4일부터 5일까지 진행했습니다.

C. 2026

앞서 map이 느리다는 추측을 했기 때문에, map을 정적 배열로 바꾸고 메모리 초과가 나는지 확인해 봤습니다. 그랬더니 매우 빠르게 AC를 받더라고요? map은 최대한 아껴서 사용해야겠습니다.

E. Kite

$A_i$에 대해 오름차순으로 정렬한 뒤 LIS를 구하면 되는 문제 같지만, $A_i$가 같은 쌍이 여러 개 있을 수 있다는 점이 걸림돌입니다. 이때는 $B_i$에 대해서 내림차순으로 정렬하여 LIS를 구하면 됩니다. 내림차순 아이디어를 떠올리지 못해서 풀지 못한 문제였네요.

결론

확실히 PS는 다양한 문제를 열심히 푸는 수밖에 없는 것 같습니다. 특히 배열을 사용하면 되는 C와 $B_i$에 대해 내림차순 정렬하는 E가 그렇게 어렵지 않았는데, 풀지 못한 점이 매우 아쉬운 것 같습니다. 어쩌겠습니까. 다음 앳코더에서는 잘 해야죠.