wnsrl1228   2년 전

저는 건물을 짓는 도중에 다른 건물을 지을 수 없다고 생각하였습니다

(테스트 케이스는 위처럼 생각해도 답이 다 나왔음)

예를 들어

1
5 3
10 50 10 20 10
2 1
3 1
4 3
5 4
1

일 경우 제가 잘못 생각한 답안은

처음 5번 건물을 짓고 + 10   

그 다음 2번과 4번을 동시에 짓고  +50

그 다음 3번을 짓고 +10

마지막 1번을 짓는 +10

해서 답이 80이 나오는 줄 알았습니다.

위처럼 생각하면 이제 코드를 어떻게 구현할지 답이 안 나옵니다.

-

하지만 제대로된 방식은 건물을 짓는 도중에도 다른 건물들을 지을 수 있기 때문에 아래의 예시처럼 됩니다.

처음 2번과 5번 건물을 짓고 

10초 뒤 5번 건물을 완성시키면 4번 건물을 짓습니다. (2번 건물 완성까지 40초 남음)

20초 뒤 4번 건물도 완성시키면 3번 건물을 짓습니다. (2번 건물 완성까지 20초 남음)

10초 뒤 3번 건물도 완성시킵니다. (2번 건물 완성까지 10초 남음)

이제 2번 건물 완성까지 10초를 마저 기다린뒤 마지막 1번 건물을 10초 동안 짓습니다.

그러면 총 10+20+10+10+10 로 60초가 나옵니다. 실질적으로 2번 건물을 지을 동안 5,4,3번 건물을 모두 지을 수 있습니다.

-

따라서 밑에는 다른 분이 남긴 예제였는데

1
5 5
10 20 30 40 50
1 2
1 3
2 4
3 4
5 4
4

답은 90이 나옵니다



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