2022 서울사이버대학교 프로그래밍 경진대회 (SCUPC) 회고

대회에서 푼 문제

문제는 A, B, C까지 풀었다. 350명 중 80등이다.

난이도와 최종으로 푼 문제

대회가 끝나고 D와 E를 추가로 더 풀었다.

플레티넘 문제까지는 다 풀려고 했지만 에디토리얼이 없어 나 혼자서 풀 수 있는 문제까지 풀었다.

🧩 D. 은?행 털!자 1

실버로 랭크되었지만 풀이를 생각해 내는 데 까지 오래걸렸다.

X 증가 순으로 탐색해야 하면서 동시에 T도 증가 순으로 탐색해야 하는 어려움이 있었다.

그래서 처음엔 DP로 생각했다가 포기했다.

보통 이렇게 탐색 기준이 2가지인 경우에는 max-heap이나 segtree를 쓰던것 같다는 생각이 바로 들었다.

결국 가장 잘 맞는것이 segtree라고 생각했다.

이게 실버 수준??

근데 진짜 문제 난이도가 "실버"인 것이 정말 이상하게 느껴졌다.

누가 난이도 테러 했나? 원래 쉽게 풀수 있는 방법이 있나? 브루트 포스 방식으로 쌉가능인가? 같은 생각이 들었고

문제를 유심히 보니.. 제약이 있어서 X와 T의 차이를 구해서 해결할 수 있었다.

어려운 기술을 쓰지 않지만 방법을 생각하기 어려운 문제였다.

🧩 E. 은?행 털!자 2

D와 같은 문제지만 조건이 조금 까다로워졌다.

제약이 사라진 것이다. X와 T의 차이를 구하기만 하는 걸로는 풀수 없다.

하 지 만! 여기서 segtree를 쓴다면? 쉽게 풀리는 문제였다.

빌드업 미쳤고

D에서 고군분투한 덕분에 정말 쉽게 풀 수 있었다. 게다가 요즘 segtree를 다시 공부하고 있어서 일석이조였다.

느낀점

진짜 재미있었다.

초보자도 D는 풀어볼만한 문제였다고 생각한다.

cost를 뺀 고려할 변수가 2개 이상일때, 어떻게 가공해야 하는지 다시한번 생각해 보게 되었다.