PS | 0710~0716 | 2022

15940

본선 팀연습 때  jjaewon9와 함께 해결한 문제.
트리에서 각 간선에 대해, 그 간선이 나누는 두 서브트리의 지름을 빠르게 구해 문제에서 원하는 최댓값을 갱신해주면된다.
루트를 하나로 고정해두면 이제 루트가 아닌 각 정점에 대해 그 정점이 루트인 서브트리의 지름과, 이 서브트리의 여집합 (정점의 부모로부터 이어진) 트리의 지름을 구하면 된다. 

서브트리의 지름을 구하는 방법 중 dp 방식이널리 알려져 있는데, 각 서브트리에서 루트로부터 가장 먼 정점과의 거리를 저장해 두고 max( max(dp(자식)), max(가장 긴 2개 다리 길이의 합))을 구하면 된다.
아래 지름을 dpD, 위 지름을 dpU에 저장하자.
dpU를 구하는 방법도 dpD와 비슷한데, 정점과 부모를 고정하고 생각하면 casework할 수 있다.
1) 부모의 dpU
2) 부모의 위로 가장 멀리 떨어진 다리, 부모의 다리(현재 정점 잇는것 제외)들 중 가장 긴 것 2개 연결
3) 부모의 자식들중 (현재 정점 제외) dpD의 최댓값
현재 정점을 포함하는 정보들은 사용불가능하므로 2번째로 큰, 3번째로 큰 값들을 저장하여 최댓값을 구해주면 된다.
차근차근 생각해서 노트에 기록해두고 구현하면 편하다.
3번째 큰 값 등을 구현하기 귀찮을 때 우선순위큐를 사용하자. 예를 들어 가장 큰 3개 값을 구하고 싶다면 최솟값 우선순위큐를 이용하면 Nlog(3) 시간에 처리할 수 있으므로 선형시간에 훨씬 구현이 편하다.

 

SCPC 1라운드

1번: 그리디 - stable sort한 후 각 이동거리를 더해주면 된다.
2번: dp - 각 블록은 Sum/k의 합을 가져야하고, 누적합 배열을 관리하면 k번째에서 몇개의 블록이 생겨야 하는지 알 수 있기 때문에 dp로 풀 수 있다. 단 Sum=0인 경우에는 nCr로 답을 구해야 한다.
3번: 관찰 - x좌표 기준으로 정렬했을 때 y좌표가 인접한 점들끼리 연결해야 하는 것을 알 수 있다. 에러점을 구하는 방법은 x좌표 기준 정렬한번, y좌표 기준 정렬을 하여 x,y 각각의 에러 좌표를 구할 수 있다.
4번: 풀이 구체화를 못했다. KMP ,
문자열 x에서 연속한 a의 그룹과 연속한 b의 그룹을 적절히 골라 문자열 y를 만들 수 있느냐 판정하는 문제. 일반성을 잃지 않고 문자열 y의 시작 알파벳을 a로 설정하자. 각 a에 대하여 왼쪽에 있는 b의 개수를 저장하고 어찌저찌 잘하면 KMP인 것을 확인할 수 있는데 문자열 끝에서 처리하는게 너무 귀찮아서 풀이를 마무리하지 않고 잤다. 서브태스크를 먼저 미는 습관, 꼭 필요한 것
5번: 안 풀었다