-
문제 난이도 미쳤네. 정해를 드디어 찾은거 같은데 이건 뭐 문제 푸는 사람보고 서커스 하라고 하는거 같습니다. 입력으로 각기 3개의 서로 다른 숫자를 가진 M개의 엔트리가 주어지는데, 그 중 겹치는 숫자가 하나도 없으면 무조건 해가 나올 수 없고 두 개 이상이면 무조건 해가 나오게 된다는 사실을 이용해 모든 엔트리에 하나의 숫자가 겹치는 경우에 대해서만 답을 찾도록 문제를 변형시키는게 첫 걸음입니다. 그 후 만약 M개의 엔트리에서 최대 총합 2개의 숫자를 제하여 각 엔트리에서 오직 하나의 숫자만 선택 될 수 있는지 여부를 확인하면 되는데, 여기서 사람들은 이제 문제를 다 풀었다 착각할 수 있습니다. 착각입니다. 나이브하게 완전탐색을 시도하면 최악의 경우 O(M^3)의 시간복잡도가 나오게 됩니다. 그래서 관찰을 더 해보면, 각 엔트리에 중복되는 수를 제하면 각기 2개의 숫자를 가지게 되는데, 여기서 숫자를 노드로 그리고 두 숫자를 포함한 엔트리를 엣지로 하여 그래프를 만들 수 있음을 알게 됩니다. 그리고 그러한 그래프에서 모든 분절점을 찾아 biconnected component로 분할할 수 있고, 그리 분할한 bc에 대해 분할정복을 할 수 있습니다.
작성자
메가스콤네노스
작성시간
22.08.22
-
답글
_Arondite_ // 사실 수학은 아니고 프로그래밍 문제인데, 이 정도 난이도에선 수학 문제에 더 가까워지긴 하더군요 ㅋㅋㅋㅋㅋ
작성자
메가스콤네노스
작성자 본인 여부작성자 작성시간
22.08.23
-
답글
통장// 문제 링크(https://www.acmicpc.net/problem/20656). 간단하게 정리하면 주어진 입력으로부터 그래프를 그려 그 그래프가 bipartite한지 대답하는 문제인데, 그 그래프의 노드를 최대 2개 제할 수 있다는게 골치를 썩히게 합니다... 일주일 넘게 머리 싸맨 문제라 좀 제가 설명을 휙휙 넘겼던거 같습니다.
작성자
메가스콤네노스
작성자 본인 여부작성자 작성시간
22.08.23
-
답글
흠...나도 수학공부 다시 해볼까...
작성자
_Arondite_
작성시간
22.08.23
-
답글
...어....네. 읽기만 해도 문제 이해 자체가 서커스 같네요(..)
작성자
통장
작성시간
22.08.22
-
답글
문제는 그리 분절점을 찾는다 하여도 최악의 경우 여전히 완전탐색으로는 O(M^3)의 시간복잡도가 나오게 됩니다. 그래서 더 관찰을 하면, 각 biconnected component는 기본 정의상 가지는 특성 중 하나로 그에 속한 모든 노드가 다시 같은 biconnected component에 속한 다른 모든 노드와 최소 하나의 사이클을 가진다는걸 알 수 있습니다. 그리고 그러한 사이클은 그에 속한 노드의 갯수가 짝수 혹은 홀수인데, 주어진 그래프가 답을 가질 수 있기 위해서는 그에 속한 각 biconnected component의 각 노드 갯수가 홀수인 사이클을 그래프 전체 총합 최대 2개의 노드를 제하여 모두 제거할 수 있어야 합니다.
그걸 구하면 문제를 풀게 됩니다. 수학적으로 미친 서커스를 하도록 요구하는 문제였네요.
작성자
메가스콤네노스
작성자 본인 여부작성자 작성시간
22.08.22
댓글 쓰기
카페 검색