BOJ 기준 11617, 21936, 16243, 18081 4문제를 5시간정도 잡고 돌았습니다. 세팅은 제가 한 건 아니고 어딘가에서 긁어왔습니다.
타임라인
(00:00~) 시작
일단 전체적으로 문제를 다 읽었습니다.
A는 적당히 정점을 추가하면서 스투라하는 문제처럼 보였고
B는 간단한 DP같았습니다.
C는 전에 제가 봤던 문제더라고요 근데 풀이는 모르고 티어는 알아서 일단 읽고 (R5) 그냥 버렸습니다.
D는 흠... 그리디인가? joisc 2025 exhibition 느낌이 나는데 자구 그리디인 것 같았습니다.
일단 제일 쉬워보이는 B를 잡았습니다.
B (00:51)
DP[i][j] : 1~i까지 결정했고, 지금 i번째 문자부터 연속된 j개 문자가 S의 prefix j개와 일치할 때, i, i+1 .. N에 대한 점수 합 최댓값.
과 같이 정의하면 될 것 같았습니다. 전이는 지금 i~i+j-1가 S에 매치되고 있으므로, 여기에 S[j+1]을 추가해 DP[i][j+1]으로 가는 경우와, 이 i를 포기하고 다른 k로 가는데 만약 i~i+j-1까지 매치되는 중에 어떤 k가 존재해서 k부터 i+j-1보다 크거나 같은 위치까지 매치되는 경우, 그런 가장 빠른 k로 전이했습니다. i와 k 사이에서 시작한 suffix의 점수는 어차피 더이상 늘어날 수 없으므로 $($i+j-1까지 정해졌는데 그 지점에 가기 전에 S의 prefix와 달라지므로$)$ DP[k][대충적당한수]로 가도 됩니다. i -> k로 가는 과정을 미리 $O(N^2)$에 전처리할 수 있으므로, $O(N^2)$에 풀 수 있습니다.
추신 : KMP가 태그에 있는데, 아마 KMP를 쓰면 전처리를 다른 방식으로 할 수 있는 것 같습니다. 암튼 전 안씀.
A (01:24)
그다음 쉬워보이는 A로 갔습니다. 문제를 좀 잘못 읽어서 좀 헷갈렸는데, 풀이는 매우 쉽습니다. 당연히 가중치가 큰 정점부터 추가하면서 답을 구합니다. 하나를 삭제할 때 나머지 정점들의 degree는 변하지 않으므로, 순서에 관계없이 모든 "차수가 2인 정점"이 사라집니다. 사실 예외가 하나 있는데, 완벽한 사이클을 이룰 경우 그친구는 마지막 한놈이 살아남습니다. 사라지는 횟수를 알면 나머지는 쉽게 처리할 수 있으므로 유파 등을 이용해 관리하면 $O((N+M)logN)$ 비스무리한 시복으로 가능합니다.
D (04:01)
사실 좀 쉬운데 괜히 고생했습니다. 깊이가 $logN$인걸 이용해 분정 느낌의 시복으로 하는 tree DP인가?라고 생각해봤는데 저장할 정보가 너무 많습니다. 그래서 정석적인 그리디로 턴했습니다. 수가 작은 정점부터 더해가면서, 이 정점을 고르는 트리가 존재하는지 판정하면 됩니다. 아니면 빼고. 다음과 같은 tree DP를 생각합니다.
DP[i][j] : 노드 i의 서브트리에서, 깊이가 j가 되게 적당한 정점을 고를 때 골라야 하는 최소 개수. 불가능하다면 대충 INF로 채워넣기.
여기서 j는 0이상 30이하입니다. 대략 로그인데 상수를 적당히 생각해서 로그보다 좀 큰 수로 잡습니다.
아무것도 정하지 않았을 때, 즉 어떤 정점도 확정으로 쓰려고 정하지 않은 상태에서의 DP는 간단한 treeDP로 NlogN에 계산할 수 있습니다. 만약 1번 정점을 쓰기로 정했다면, 그 정점부터 부모를 타고 올라가면서 그 DP만 적절히 갱신해주면 됩니다. 만약 이후 DP[root][i]의 최솟값이 K보다 크다면 그 정점은 쓸 수 없는것이고, 아니라면 쓸 수 있습니다. 쓸 수 없다면 DP를 적당히 롤백해줍니다. 매 시행마다 $O(logN)$번 부모를 타고 올라가고, 각 노드마다 갱신해야 할 DP값이 $O(logN)$개이므로 $O(Nlog^2N)$에 해결할 수 있습니다.