pjshwa   5달 전

코드가 길지만... 요약을 해보겠습니다.

  • M개의 합동식 정보를, N개의 배열 원소를 잇는 간선 정보로 생각
  • 모든 배열 원소를 알 수 있는 최소 cost 는, 연결 요소별로 가장 싸게 reveal 할 수 있는 배열 원소의 cost 의 합
  • 연결 요소 안에 cycle 이 존재하지 않을 경우, 가장 싸게 reveal 할 수 있는 배열 원소에 1을 무조건 대입 후 간선별 ci 정보를 통해 나머지를 알아냄
  • 연결 요소 안에 cycle 이 존재할 경우
    • 가장 싸게 reveal 할 수 있는 배열 원소의 값을 미지수로 둠 (x 라고 가정)
    • 나머지 연결 요소의 원소 값들은, 간선의 ci 정보에 따라 x 를 이용한 식으로 나타낼 수 있음.
      • 하나의 배열 원소의 값이 x 일 경우, 이 원소와 weight (ci) 6 으로 연결된 다른 원소의 값은 6 - x 이다
    • 이렇게 원소 값들을 채워 나가는 과정에서 cycle 이 검출될 경우 다음과 같은 방법으로 미지수 값을 알아낸다
      • 미지수 부호가 음수인 원소들끼리 만났을 경우 (예: a - x, b - x) a + b - 2 * x ≡ ci (mod m) 를 만족하는 x 의 값을 후보군으로 지정
      • 미지수 부호가 양수인 원소들끼리 만났을 경우 (예: a + x, b + x) a + b + 2 * x ≡ ci (mod m) 를 만족하는 x 의 값을 후보군으로 지정
      • 미지수 부호가 다른 원소들끼리 만났을 경우 (예: a + x, b - x) a + b ≡ ci (mod m) 를 만족하지 않으면 바로 프로그램 종료, 만족한다면 아무것도 하지 않음
    • 위와 같은 방법을 통해 후보군에 속해 있는 원소가 1개 이상 있을 경우 이 값을 가장 싸게 reveal 할 수 있는 배열 원소부터 쭉 대입하고, 없다면 -1 을 출력하고 프로그램을 종료한다.

랜덤 데이터를 생성하여 계속해서 테스트 해보고 있는 중인데, 코드에 어떤 오류가 있는지 모르겠네요. 도와주시면 감사하겠습니다.

doju   5달 전

x의 후보가 유일하다면 카드를 뒤집을 필요가 없을 것 같습니다.

pjshwa   5달 전

그러네요!! doju 님 감사합니다.

댓글을 작성하려면 로그인해야 합니다.