오늘의 PS (23) - 220822~220905

지난 포스트에서 글을 자주 쓰겠다고 했는데, 바쁘다고 미루다 보니 또 2주동안 글을 쓰지 않았다.

그동안 있던 SCPC 본선과 SUAPC는 별도의 글을 올릴 예정이다.

2주동안 있었던 코포랑 앳코더는 다 언레라 진지하게 치지 않아서 여기 올리기엔 좀 그런 것 같아 백준에서 푼 문제들만 정리해보려 한다.

 

2021 홍익대학교 프로그래밍 경진대회

 

23320 홍익 절대평가

그냥 구현. 문제가 친절해서 실수도 필요 없고 정렬도 필요 없다.

 

23321 홍익 댄스파티

그냥 구현. 귀엽긴 한데 무슨 말인지 알아보기가 좀 힘들었다.

 

23322 초콜릿 뺏어 먹기

코포식 그리디 문제이다. 풀이는 자명하게 찾을 수 있다.

 

23323 황소 다마고치

역시 코포식 그리디 문제이다. 어느 경우가 최적인지는 잘 생각해보면 알 수 있고, 구현도 builtin 함수를 쓰면 한 줄에 가능하다.

 

23324 어려운 모든 정점 쌍 최단 거리

최단거리 문제인 척 하는 BFS 문제이다. 적혀있는 것만 잘 보면 어렵지 않게 답을 구할 수 있다.

 

23325 마법천자문

교내대회를 위한 교육적인 양산형 DP 문제이다. 그냥 잘 하면 된다.

 

23326 홍익 투어리스트

비슷한 문제를 많이 풀어봤으면 어떤 자료구조를 사용해야 하는지 바로 알 수 있다. 예외도 크게 어렵지 않다.

 

23327 리그전 오브 레전드

웰노운 식정리를 하면 된다. 

 

23328 마을 구하기

처음 봤을땐 간단한 것 같아서 그냥 짰는데, 생각보다 경우의 수가 많았다. 생각을 충분히 하고 코딩하는게 좋은 문제인 것 같다.

 

23329 구슬 발사기

8방향으로 간선을 연결해준 후 다익스트라를 돌리면 되는데, 구현할 때 여러모로 킹받는 부분이 좀 있다. 

 

총평

전체적으로 균형잡힌 셋이었던 것 같다. 웰노운 문제들은 확실히 웰노운이고, 애드혹 문제들은 확실히 애드혹인 점이 인상깊었다. 특히, C와 D가 "적절히 쉬운 실버 그리디" 인 점이 좋았던 것 같다. 문제를 만들어 보면 알겠지만, 쉽고 새로운 실버 문제 만드는 게 제일 어렵다..

 

2022 중앙대학교 CHAC (ChAOS Hello2022 Algorithm Contest)

 

24389 2의 보수

그냥 하라는 대로 구현을 해도 되고, 관찰을 한 후 builtin 함수를 써도 된다. 난 후자로 했다.

 

24393 조커 찾기

하라는 대로 하면 된다. 입력이 약간 불편한데, 한 줄에 주어지는 수들의 합이 무조건 27이라는 점을 이용해 구현하면 된다.

 

24392 영재의 징검다리

그냥 2차원 DP를 쓰면 된다.

 

24390 또 전자레인지야?

그냥 1차원 DP를 쓰면 된다.

 

24392 귀찮은 해강이

같은 말을 너무 많이 쓰는 것 같지만, 하라는 대로 하면 된다.. BFS/DFS보다는 UF가 구현이 편하다.

 

24395 명진이의 신년계획

지문만 읽고는 뭘 하라는 건지 잘 몰랐는데, 예제 설명을 보고 3차원 냅색임을 알아챘다. 출력에서 요구하는게 약간 독특한데 그냥 다 넣고 정렬해주자.

 

24394 123456789점

의도가 뭔지 잘 모르겠다. 저 어지러운 식에 의미가 있는지는 모르겠지만 \(a\)를 고정하고 생각하면 \(O(TN)\)에 문제를 풀 수 있다.

 

24396 푸앙이와 별

세팅도 깔끔하고, 풀이도 깔끔한데 왜 되는지를 모르겠다. 1번 정점부터 시작해 넣을 수 있는 정점을 넣는 식으로 구현하면 되는데, 이는 (현재 탐색된 정점의 수) = (나와 끊긴 정점 중 탐색된 정점의 수) + (나와 연결된 정점 중 탐색된 정점의 수)임을 이용해 1번과 2번을 관리하고, 3번이 1 이상인 정점들을 큐에 넣어주면 된다. 진짜 어려운 부분은 시간 복잡도 증명인데, 대충 최대 거리가 \(O(M/N)\) 정도 이고 각 차례에 \(O(N)\)만큼의 루프를 돌아 잘 되는 것 같다.

 

24397 말해 xor NO!

웰노운 이진 트라이 유형이다. 그래도 해당 자료구조를 쓰는 문제들 중에선 어려운 편인 것 같다. 경우를 잘 정리해주면 해결할 수 있다.

 

총평

초중반부 문제들은 너무 웰노운이라 좀 그랬지만, 후반 문제들 (특히 H)는 나쁘지 않았던 것 같다.

 

백준에서 다른 문제들도 좀 풀긴 했는데, SCPC 대비용 알고리즘 복습을 위한 문제들이었기에 생략한다. 어려운 알고리즘 많이 외워갔는데, 정작 SCPC에서는 IQ 차이로 벽느끼고 망해버렸다.