srand   1년 전

지문중에 아래 내용은 .. room 1에 있는 청소기의 이동 비용은 1인 것 같은데 2라고 적혀 있어서

뭔가 잘못이해 하고 있는게 아닐까 해서 제대로 이해한게 맞는지 질문 드립니다.

As shown in the figure, moving from (a) to (b) and to (c) has the same cost that is 1 (moving cost of the cleaner in room 1 is 2).

- 이동은 다른 청소기 위치를 포함하여 몇칸이든 이동할 수 있고 비용은 청소기의 이동 비용(C)만큼 든다.

- 청소는 청소기의 1회당 먼지 총량에서 1회당 흡입력(P) 만큼 청소할 수 있고 비용은 고정비용 1만큼 든다.

방에 먼지가 총 10이고, 흡입력이 3이면 총 ceil(10/3) 만큼 청소해야 하며 청소 횟수만큼 고정비용이 든다.

1
2 9
6 0 3
1 8 2
0 0 0 0 0 0 0 0 11

1번 청소기가 이동한다면 : 이동 비용(3) + 흡입 비용(2) = 5
2번 청소기가 이동한다면 : 이동 비용(0) + 흡입 비용(11) = 11


1
2 9
6 0 3
1 8 2
0 0 0 0 11 0 0 0 0

1번 청소기가 이동한다면 : 이동 비용(3) + 흡입 비용(2) = 5
2번 청소기가 이동한다면 : 이동 비용(2) + 흡입 비용(11) = 13

어느 부분이 틀렸을까요?

zenith82114   1년 전

  • 인접한 칸이 비어 있으면 1 cost를 내고 그 칸으로 이동할 수 있다.
  • 인접한 칸에 다른 청소기가 있고 그 너머의 칸이 비어 있으면 1 cost를 내고 그 청소기를 건너뛰어 그 빈칸으로 갈 수 있다.

그래서 마지막 그림에서 (a)->(b)와 (a)->(c)가 둘 다 1 cost라는 의미인 것 같습니다.

srand   1년 전

vacuum:	  A   B
room  : 0 1 2 3 4 5

청소기 A의 이동비용이 C라고 할 때
    1번방 -> 0번방 이동 : C * 1
    1번방 -> 2번방 이동 : C * 1
    1번방 -> 3번방 이동 : 이동 불가
    1번방 -> 4번방 이동 : C * 2
    1번방 -> 5번방 이동 : C * 3

이네요.

1. 이동할 때 다른 청소기가 있으면 이동 X

2. 이동할 곳에 다른 청소기가 있으면 그 너머 빈 곳으로 이동. 단 비용은 C (2칸 이동이지만 1칸 이동 비용만)

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