doju   3년 전

  • 그 길이만큼 위, 아래로 터지게 된다. → 그 길이만큼 상하좌우로 터지게 된다.
  • 답이 존재하는 입력만 주어지는지 확인하고, 이를 입력 조건에 명시해 주세요. 예를 들어 아래와 같은 데이터는 답이 존재하지 않습니다.
  • 사용하는 폭탄의 개수가 최소가 되어야 하는지 여부를 명시해 주세요.
  • 자연수 K → 정수 K

doju   3년 전

만약 폭탄을 최소로 사용해야 하는 문제라면, 도시가 0과 2로만 이루어져 있고 K = 1일 때 이 문제는 임의의 격자 그래프에서 minimum dominating set을 찾는 문제가 됩니다. 이 문제는 NP-complete임이 증명되어 있습니다(Clark, Colbourn & Johnson (1990).). 또한 K = ∞인 경우는 NP-hard임이 증명되어 있습니다(Alpert & Roldán (2021).).

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