250906 - LGCPC 2025 예선 후기

1솔 2긁 111점. 스코어보드 프리즈가 풀리지 않은 상태라 순위는 더 내려갈 듯싶다.

---

푼 문제

A - 서브태스크 점수 100점

처음 문제를 읽고 꽤나 오래 갈피를 못 잡았던 걸로 기억한다. 자잘하게 구현할 것들이 많아 보였고, 글도 잘 안 읽혔다. 그래서 우선 코드를 짜며 생각해보기로 했다. 문제별 가능한 서브태스크 점수의 경우는 위상 정렬로 구해보고, 경우의 수는 DP로 구하면 될 거 같았다. 그런데 서브태스크 점수의 경우의 수를 구하는 과정에서 위상 정렬만으로는 뭔가 부족하다는 것을 깨닫고, 문제를 다시 읽어보니 범위가 상당히 작아서 백트래킹으로 가능한 모든 서브태스크 조합의 수를 구했다. 

B - k 혐오자 8점

우선 8점 짜리 서브태스크는 나이브한 풀이로 정말 쉽게 긁을 수 있어서 바로 긁었다. 그리고 문제를 좀 쳐다봤다. BOJ 1019번에서의 아이디어를 사용하면 되려나? 싶은 생각이 들었지만 아니라는 것을 깨달았다. 단순히 k * 10^c를 뺀다고 되는 문제가 아니라 앞의 숫자들을 전부 당겨줘야하고, 그러면 수가 크게 변하기 때문. 이걸 깨닫고 나머지 문제를 긁으러 갔다.

D - 신호기 3점

제일 쉬운 서브태스크만 긁을 생각으로 읽었다. B와 다름 없이 백트래킹으로 쉽게 긁을 수 있어 보여서 바로 코드를 짰다. 근데 반복문 범위 잘못 잡아서 1번 틀렸다.

---

못 푼 문제

C - 트리 위의 표식

서브태스크 긁을 생각으로 문제를 읽었는데 k의 범위가 서브태스크에서 제한되지 않는 걸 보고 도망갔다. 지금 생각해보니 그냥 짰으면 됐을수도 있겠다.

B - k 혐오자

남은 시간 동안 본선 진출 확률을 높이기 위해 할 수 있는 건 B를 푸는 것 말고는 없어보여서 B를 들여다봤다. 가만보니 N의 자릿수 제한이 10만자리로 꽤나 컸다. 이 때 Digit DP로 접근하면 풀 수 있겠다는 생각이 들었다. 하지만 가장 큰 문제가 남아있었다. 내가 Digit DP 문제를 풀어본 적이 없고, 그저 개념만 알고 있다는 것이었다. 그래도 포기하지 않고 남은 시간동안 열심히 점화식을 세우다보니 대회가 끝났다.

---

후기

사실 2솔도 못하고 본선 진출을 바라는 건 꿈이 너무 크지 않나 싶다. 그래도 처음 A번을 보고 한 문제도 못 맞는 거 아닌가 하는 걱정이 들었는데, 다행히도 1솔 + a의 성적을 거뒀다. 그리고 긁기만 할 수 있는 문제는 빠르게 정해서 부분 점수라도 빨리 받는게 효율적이겠구나 싶은 생각도 들었다. 기대를 별로 안 한 상태로 참가해서 그런지 기대 이상의 즐거움을 얻은 대회.