2학년 2학기 알고리즘 과제_6주차(백준_1098번:쌍둥이 마을)

1098번: 쌍둥이 마을    문제쌍둥이 마을은 두 마을의 사람들 간에 커뮤니케이션과 문화적 교류를 위해서 만든 것이다.따라서 정부는 마을 사이에 쌍둥이 마을을 많이 제정하려고 한다. 물론 가능한 모든 마을의 쌍을 쌍둥이 마을로 제정하면 좋겠지만, 다음과 같은 규칙을 지켜야 한다.각 마을은 P개 이하의 쌍둥이 마을을 가진다. 쌍둥이 마을이 없을 수도 있다.각 쌍둥이 마을의 거리는 적어도 D이다.두 마을이 (x1, y1) 과 (x2, y2) 에 있을 때, 두 마을 사이의 거리는 |x1-x2| + |y1-y2|이다.정부는 되도록이면 많은 쌍둥이 마을을 만들려고 한다. 만약 이러한 것이 여러 가지라면, 쌍둥이 마을 사이의 거리의 합을 최소로하는 것을 선택한다. 각 마을의 위치와 P와 D가 주어질 때, 쌍둥이 ..

2024.11.16