Ucpc 2020 문제를 맛보았다 (21.04.20 기준)

(실제 대회 응시자가 아님을 밝힙니다.)

 

요즘 Ucpc, icpc, KOI 등 대회 문제들의 질이 좋음을 깨닫고

대회 문제들을 여러개 풀어보고 있다.

UCPC 2020 본선 문제들은 역시 괴수들을 위한 대회라 난이도가 상당히 어려웠다..

 

C번은 계속 틀려서 맞왜틀 엄청 하고, 현재 맞춘 상태이다.

원래 내가 ps 하는 목적이 코테 통과 및 취준을 위해서인데,

아직 취준하려면 멀기도 했고 일단 군생활동안은 재미삼아 ps하자는 주의이기 때문에 

대회 본선 진출 목표(SCPC든 UCPC든)로 공부중이다.

 

일단 문제들이 되게 마음에 들기 때문에 문제들을 간략하게 포스팅해볼 생각이고,

후에 D번, L번, 그리고 실력이 된다면 G번, I번도 풀어보고 포스팅해볼 생각이다.

---

A. 전단지 돌리기 

사용 알고리즘: dfs (Gold IV)

www.acmicpc.net/problem/19542

19542번: 전단지 돌리기

UCPC 2020중 유일하게 풀만했던 문제이자 유일하게 한번에 맞춘 문제이다.

우선 문제가 딱 봐도 트리니까 dfs를 사용해야 할 것처럼 생겼다.

거리가 D 이하인 모든 노드에 전단지를 돌릴 수 있으므로,

각 노드마다 리프노드에서부터의 거리를 재귀적으로 구해주면 되겠다.

 

이후, dfs를 한 번 더 돌면서 답을 구해준다.

역시 재귀적으로 답을 구한다.

이 때 다시 되돌아오는 거리까지 구해줘야 되므로 구한 답이 2를 곱해준다.

 

 

(C++17 코드)

boj.kr/22ad94d3e0114446976bac3a35fb8d33

공유 소스 보기

---

B. 던전 지도

사용 알고리즘: 투 포인터 (Gold I)

www.acmicpc.net/problem/19543

19543번: 던전 지도

처음 볼 땐 DFS문제인 줄 알았으나,

범위 보고 절대로 dfs로 하면 안되겠다는 느낌이 들었다.

 

그런데 이 문제 생각보다 구현할 것도 많고, 투포인터임을 파악하기도 쉽지가 않았다.

그리고 가장 어이없는거... 도착점이 우측 하단이 아니고 우측 상단이어서 쓸데없이 맞왜틀을 더했다.

진짜 문제 잘 읽는 습관, 문제를 빠르게 정확히 읽는 습관을 기르자.

 

잘 보면 위에 행에서 도착못하는 구간은, 아래 행에서 살펴볼 필요가 없다.

따라서 구간으로 나타낼 수 있고, 모든 노드마다 dfs를 할 필요가 없다.

근데 이걸 파악해도 시간초과가 굉장히 잘 난다.

구현이 좀 빡빡한 면이 있기도 해서 대회 당시 정답률이 C번보다 더 낮았다고 한다.

boj.kr/5d0f80de9ec44a55929c6269e5b7730d

공유 소스 보기

---

C. 함수 복원

사용 알고리즘: 수학, 트리, 그래프 이론 (Platinum V)

www.acmicpc.net/problem/19544

19544번: 함수 복원

사진으로 심정을 대체한다.

www.acmicpc.net/board/view/67329

글 읽기 - 반례가 무엇이 있을까요?

이 질문글에 내 접근법, 임의로 만들어본 테스트케이스(반례), 그리고 맞왜틀한 어처구니없는 이유가 모조리 다 담겨있다... (p_ce1052님 정말 감사합니다.)

하... 진짜 MOD로 나누는 실수랑 index실수때문에 이틀을 꼬박 고생할줄이야 멍청하기 그지없다

 

---

앞으로 풀어볼 것

UCPC 2020: L번

Good Bye, BOJ 2020!: D, E번

Good Bye, BOJ 2019!: E번

KOI 골드문제들

USACO (농장 소덕후 John덕후) solvedac기준 골플 문제들 

 

그래프, dp, ds (segtree 포함) 문제들 위주로 집중공략하려고 한다.

일단 Spring boot, JPA 공부랑 비중도 늘려야되기 때문에 천천히 느긋하게 풀어보려한다.