2022 ICPC Sinchon Summer Algorithm Camp Contest Open

https://www.acmicpc.net/contest/view/843

2022 ICPC Sinchon Summer Algorithm Camp Contest Open

해설

 

 

 

 

 

 

 

---

총 6문제 (A~E, H)를 풀었습니다.

 

A

머리 좀 굴려보면 'a, b, c중 최솟값'이 정답이 됨을 알 수 있습니다.

 

H

테스트케이스 T에 대해 O(T) 알고리즘이라 A랑 똑같이 풀었습니다. 다만, T <= 10만이기에 StringBuilder로 출력 횟수를 줄여 수행 시간을 줄였습니다.

어쩌다보니 참가자 중 가장 먼저 풀었네요 ㅎㅎ

 

B

단순 구현

 

C

요구 피로도가 작은 장신구부터 그리디하게 만들기

 

D

단순 구현: 스택에서 '열린 괄호 - 닫힌 괄호의 개수'를 int값으로 저장하는 느낌을 활용하면 구현이 더 편할지도?

 

E

트리는 제 약점 중 하나입니다. 특수한 그래프라 편하다고 하기엔 숙련도가 너무 떨어집니다. a 50만개가 적당히 퍼져있는 트리를 생각해보면, 모두 돌아보면서 문자열을 concat하면 O(N^2)이 떠서 안 됩니다. 이게 맞는지 모르겠는데, bfs로 가장 뒤에 있는 알파벳을 모두 찾아주었습니다.

-> 해설 보니 BFS 요구한 게 맞더라고요.

 

 

---

못 푼 문제 복기

 

F

한 쪽 구석으로 몰아제껴도 영향 없는건 제껴놓고 / 나머지는 비교하기 이런 식인거 같은데, 구현이 좀 어려워보입니다.

-> 그리디 느낌으로 정리하면 될 거 같았는데, case-work 빡센 DP 문제였네요.

 

G

다익스트라같긴 한데, edge가 최대 400억개 언저리로 나올 수 있을 거 같아서 못 하겠네요. 백준 2887번: 행성 터널의 느낌으로 간선을 덜 만들어야 하는 거 같은데...

-> '행성 터널'처럼 min(x 차이, y 차이) 간선은 x or y가 인접한 경우만 만들면 됩니다. 

-> z값 처리는 N+1, ... , N+K 번째 가상의 점을 만들어, i번째 정점의 z값에 대하여 i에서 N+1+(z mod K), N+1+((K-z) mod K)에서 i로 가는, 길이가 z인 단방향 간선을 만듭니다. 약간 백준 5214번: 환승 문제의 아이디어랑 비슷하네요.

-> 간선이 총 4N개 만들어지기에, 다익스트라를 수행할 수 있습니다.

 

이 뒤로는 어려워서 생략