tjdgnsqn3   2달 전

예를들어 100개 분열을 시작하자 하면 매 단위시간마다 100이 늘어나는 걸까요?

tjdgnsqn3   2달 전

우선순위 큐와 bfs를 통해 열쇠 위치에 도착했을 때, 0으로 갱신하면 왜 정답이 안 되는지도 알 수 있을까요?

1. 시작점에서 무한개의 로봇을 뿌렸다고 가정

2. 첫 열쇠에 도착하는 로봇은 (1) 로부터 왔을 것임

3. 2번째는 첫 열쇠로부터 가까우면 첫 열쇠에서 왔을 것이고, (1)에서 왔을 거임

4. n번째는 1~n-1에서 가까운 로봇이 도착했을 것이다.

멈춘다면 위 단계가 성립하는거 같은데, 문득 멈추지 않는건가 싶어서요.

pjshwa   2달 전

아래와 같은 경우에 답을 잘못 출력합니다. (1, 4) 의 K로 이동하여, 거기서 로봇을 복제하여 (1, 1) 로 하나 이동시키는 것이 최적입니다.

tjdgnsqn3   2달 전

7 2

1111111

1K11K11

1000011

1110111

11S0111

1111111

1111111

(시작점, 좌표) pair를 이용해서 처리했지만 틀리는군요..

더 추가로 고려할만한 사항이 있을까요?

pjshwa   2달 전

반례를 하나 더 드립니다. M+1 개의 정점이 있는 완전 그래프에서, 간선의 비용 합을 최소화하도록 M 개의 간선을 고르는 문제로 접근해 보시면 좋을 것 같습니다.

tjdgnsqn3   2달 전

풀었습니다. 감사합니다!

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