PS를 어떻게 할까 생각하다 어디서 본 좋고 재밌는 방법이 떠올라서 도전해본다. 랜덤으로 문제를 뽑아서, \(30 + max(0, (x-G1)*5) \) 분 안에 문제를 푸는 데에 성공하면 티어를 하나 올리고, 풀지 못하면 내린다.
자세한 사항은 https://blog.naver.com/bnb2011/222621250928 를 참고하시면 된다.
손도 풀 겸 G5부터 시작했다.
G5인데 풀이가 바로 떠오르지 않아 당황했다. 한 5분정도 문제를 천천히 살펴보니 직사각형의 크기가 주어진다는 것을 알 수 있었다. 왼쪽 변의 좌표를 고정하고, 해당 x좌표에 들어오는 점들을 모은 후 스위핑해주면 된다. 이건 약간 멍청한 풀이고, 똑똑한 다른 풀이도 꽤 있는 듯 하다.
그냥 흔한 골드 격자 DP이다. 왼쪽 아래에서 시작한 경우와 오른족 아래에서 시작한 경우를 모두 구해준 뒤 합의 최댓값이 답이 된다. 구현을 좀 말려서 오래 걸렸다.
제한과 문제를 잘 보면 그냥 플로이드 문제라는 것을 알 수 있다. 양방향 길인 경우 두 방향 모두 가중치가 0인 간선을, 일방통행 길인 경우 역방향에만 1의 가중치를 주고 돌리면 된다.
처음에 선분 교차 문제인 줄 알고 좀 쫄았다. 선분이 변에 평행하게 주어지기 때문에 벽을 잘 세워준 후 BFS를 돌리면 된다. 구현이 귀찮아서 좀 오래 걸렸다.
골드 상위에서 흔하게 볼 수 있는 전형적인 트리 DP이다. 고르는 경우에는 자식을 모두 고르지 않아야 하고, 고르지 않는 경우에는 이득이 되는 자식만 골라주면 된다.
포함배제 + 수학으로 푸는 풀이가 있고, 노트에 있는 그림대로 DP를 하는 방법이 있다. 난 전자가 바로 안 떠올라서 후자를 사용해 \(O(N^3)\)에 풀었다. 난이도는 비슷한 것 같다. 이거 풀 때 솔브닥 디코에서 사람들이 재미있는 얘기를 하길래 구경하느라 좀 늦었다.
G5부터 시작하니까 손이 풀리긴 했는데 별로 얻어간 것은 없었다. 다음에는 P4부터 시작한다.
'PS > 랜디' 카테고리의 다른 글
| 업다운 랜디 (2) - 230612 (0) | 2023.06.12 |
|---|