BOJ Random Defense 2일차 (240526)

코포 이슈로 하루 쉬고 이어서 문제를 풀었다. 코포는 엄청 절었는데 다행히 점수는 많이 안 떨어졌다.

 

요약

 

11464. Hacking the Screen (Gold IV, 36:18)

 

 

1일차에 이어 PASSED가 하고 싶게 생긴 녀석이 첫 문제로 나왔다.

그래도 티어답게 나름 친절한 구석이 있어서 그냥 짜기로 했다. 풀고 나서 보니 python의 eval인가 하는 함수로 편하게 하는 방법도 있다고 한다. 그게 뭔데..

 

 

15625. Paprike (Gold III, 4:18)

 

웰노운 트리 DP 유형이다. 합이 큰 자식부터 그리디하게 잘라 주는 과정을 반복하면 된다. 골3치고는 어려운 것 같아서 기여했더니 골2가 되었다.

 

2155. 삼각형의 최단 경로 (Gold IV, 13:10)

 

각 삼각형을 2차원 좌표계에 잘 대응시킨 후 \(L_{\infty}\) 거리를 구하면 된다. 좌표를 구하는 것도, 좌표를 구한 후 최단거리를 구하기도 티어에 비해 어려웠던 것 같다.

 

4835. Walk in the Park (Gold I, 11:56)

 

X축 또는 Y축을 공유하는 인접한 나무들을 보며 사이에 길이 있는지 set 등으로 확인해주면 된다. 양 끝에 있는 나무 처리에 유의하자. 옛날 문제라 ML이 작아서 2번 틀렸다.

 

2812. 크게 만들기 (Gold III, 4:51)

 

교육적인 그리디 문제이다. 우선 \(K\)개를 지우는 것이 아닌 \(N-K\)개를 남기는 것이라 생각하자. 각 숫자를 고를 때 가장 앞에 있는 9부터 0을 차례대로 보며, 해당 수를 골랐을 때 남은 개수 만큼 고를 수 있을지 판별하면 된다. 구현은 queue를 이용하면 되며, 스택 풀이도 있는 것 같다.

 

19488. Championships (Gold II, 10:02)

 

문제를 요약하자면 크기가 최대이고, 각 정점의 차수가 \(d\) 이상인 가장 큰 subgraph의 크기를 구하면 된다. 비슷한 유형을 본 적이 있어서 빠르게 풀었다. 우선 차수가 \(d\) 미만인 정점들은 사용될 수 없으므로 그래프에서 삭제하고, 위상정렬에서 하는 것과 비슷하게 인접한 정점의 차수를 줄이며 \(d\) 미만이 되면 삭제하는 것을 반복하자.

이러한 과정을 마치고 나면 조건을 만족하는 몇 개의 subgraph들이 남을 텐데, DFS/BFS를 이용해 이 중 크기가 가장 큰 것을 고르면 된다. 풀이 과정이 최근 PPC 문제인 저체온증이랑 비슷한 것 같다. 두 문제 모두 추천합니다.

 

 

첫 문제를 보고 탈주가 마려웠지만 뒤 문제들이 다행히 잘 나와서 숙제인 1500 레이팅을 빨리 찍을 수 있었다.