Wonseok Shin | 8월 3-4주차 Weekly PS

Back to : ps-weekly

Contents

August 16 - August 31, 2021

이 글에 구현코드 링크가 없더라도 PS 레포 링크 에 가서 대회 단위로 들어가면 보통 올려놓은 코드를 볼 수 있습니다.

BOJ의 문제 중 [출처] 에 대회명이 적혀있지 않으면 제 레포에서는 BOJ Original에 있습니다.

읽는 사람이 문제를 읽고 조금 생각해봤다고 가정하고, 대략적인 아이디어만 간단히 적을 생각입니다 ㅎㅎ

Recent Updates

난이도 Platinum V
Bitmask DP를 하면 됩니다. dp[BIT][REM] 을, BIT 에 해당하는 비트마스크를 붙여 나머지 REM을 만드는 경우의 수로 정의하고, 아직 쓰지 않은 원소들을 DP로 잘 관리합니다.
자세한 것은 코드 참고.

난이도 Platinum IV
가중치 없는 그래프의 인접행렬 A에 대해, $A^n$을 계산하면, 그 $i, j$ 번째 칸은 $i \to j$ 로 $n$개의 간선을 사용해서 도달하는 방법의 경우의 수에 해당한다는 사실이 잘 알려져 있습니다.
가중치가 5 이하이므로, 정점을 복사하는 트릭을 사용합니다. 만약 1번 정점에서 2번 정점으로 3의 시간이 걸린다면, $(1, 0)$ 에서 $(2, 0)$ 으로 그어주는 것이 아니라, $(1, 0)$ 에서 $(2, 2)$ 로, $(2, 2) \to (2, 1) \to (2, 0)$ 으로 가게 해서 3개의 간선을 거치도록 강제합니다.
이제 위 사실을 사용할 수 있습니다.

난이도 Platinum V
대결에서 승리한 쪽이 승천해버리기 때문에 한 노드를 두 번 포함할 수 없습니다.
즉… 대진표가 Spanning tree를 이루어야겠습니다.
주어진 점수 함수로 complete graph를 만들고, 그 maximum spanning tree를 쓰고 싶습니다.
그런데, 이 트리로 올바른 대진표를 만들 수 있을까요?
네. DFS를 따라 돌면서, 리프 노드와 리프가 아닌 노드 간의 경기에 대해서는 리프 노드가 승리하고 승천해야 합니다. (리프가 아닌 노드는 나중에 또 써야 하므로). 이제, 새롭게 리프가 된 노드가 있다면 이 노드는 자기 parent 노드와의 대결에서 승리해서 승천해도 됩니다.
DFS를 이용하면 쉽게 구현 가능합니다.

난이도 Platinum I
솔직히 이정도로 어려운지는 잘 모르겠습니다.
Trie를 골자로 한 그래프를 만듭니다. 단, autocomplete 기능을 이용할 수 있으므로 문제의 정의에 합당하게 TAB키를 길이가 1인 간선으로 표현해주고, BACKSPACE키도 길이가 1인 간선으로 표현해 줍니다.
이렇게 만든 그래프 위에서 BFS를 돌려서, 모든 노드로 갈 수 있는 최단 경로의 길이를 미리 계산합니다.
이제, query string이 주어지면, 이 query string의 어디까지를 trie 위에서 찾을 수 있는지 보고, 그 최단 경로를 따 온 다음, 나머지는 일일히 타이핑해주면 끝입니다.
구현량이 많지만 각각을 따로 구현해서 합칠 수 있으므로 별로 어렵지는 않습니다. 저는 구현의 편의를 위해 트라이와 그래프를 따로따로 만들었지만, 구현을 조심해서 한다면 트라이를 따로 만들지 않고 바로 적절히 그래프를 (트라이를 뼈대 삼아) 구현하면 됩니다.