kthng   2달 전

드래곤을 모두 죽이고싶습니다.

1. 라벨링하고,

2. 각각 라벨에 해당하는 도시들간의 거리를 구한다.

3. 각 라벨링된 도시묶음에 필요한 최소 용사 수 ..??

4. 최소 용사수들의 합이 우리가 필요한 용사의 수.


1,2,4는 가능할 것 같은데.. 3번은 좀 생각해봤는데 아이디어가 떠오르질 않네요 ㅜㅜ

수식으로 똭 나타낼 수 있을 것 같은데..

3.1 자라나는 머리의 최소값 <- 이건 아닌것같구.. 테스트케이스를 보면 용사들이 0분째부터 공격을 시작하네요 ㅜㅜ 1분째부터 공격하는거면 할만했는데

3.2 3.1의 값을 결정하는 도시의 최초 머리개수 + 두번째 자라나는 머리의 최소값(3.1의 값을 결정하는 도시의 최초 머리개수가 자라나는 머리 갯수보다 작다면) <- 이것도 역시 아닌 것 같습니다. 거리는 어떡할것이며...


이문제 어떻게해결할까요..?

힌트나 유사한문제 있을까요?

noeffserv   2달 전

방금 풀어봤는데 도시들간의 거리는 구할필요가 없네요. 대신 말씀대로 도시묶음은 알아야하구요. 

힌트로는 제가 풀었을때 이용한 식을 드릴게요..

a += min(f[i], max(0, N[i] + 1 - a)) (이때, f[i]는 min(S[i], N[i] + 1))

a는 도시묶음 마다 나오는 값이구요. 최종답은 a를 모두 합한 값이 됩니다.

kthng   2달 전

우앙 답변 고마워요!!

역시 수식으로 똭 나오는군요 멋있습니다 ^^bb

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