nhn 4번 무슨 알고리즘인가요??

[아라인(223.38)]

설마 mcmf는 아니겠죠??

문제 읽으면서 mcmf와 bfs 떠올렸는데

bfs 구현하다가

배아파서 똥싸러갔어요.

여튼 4번 bfs 맞나요?

mcmf 느낌이 강하긴한데

[익명(221.147)]

유량 알고리즘을 전부 아는게 아니라서 저는 메모이제이션으로 풀었어요

[아라인(223.38)]

이게 메모이제이션+ 우선순위큐면 될것같긴한데 문제가 mcmf 느낌이왤케 강하죠ㅋㅋㅋㅋ

[익명(221.147)]

지금 알고리즘을 읽어보고있는데 mcmf로 풀수있다면 더 깔끔하게 풀릴 것 같네요

[익명(221.147)]

저는 이 알고리즘을 몰라서 메모이제이션 하는 벡터가 2개였고 연산자 우선순위를 3개 정의했어야 했어요 큐 순환 비교랑 유량 우선순위 비교랑..

[익명(221.147)]

이런식의 메모이제이션은 이문제의 경우 음수가 없는 벨만포드처럼 풀릴 수 있는데 실제로 시간복잡도가 mcmf가 더 효율적이라고하니 메모이제이션의 경우 TC에서 터져서 부분점수를 받거나 틀리게 될 수도 있겠네용..

[익명(221.147)]

시작점부터 bfs처럼 위상형으로 다음 인덱스 우선순위 큐에 넣고

[익명(221.147)]

오더값으로 선점되면 업데이트하고 똑같으면 예외상태니가 일단 카운팅만 해주면 대요 그리고 결과에서 카운팅값보고 결정하면대요