1005번 - ACM Craft
저는 건물을 짓는 도중에 다른 건물을 지을 수 없다고 생각하였습니다
(테스트 케이스는 위처럼 생각해도 답이 다 나왔음)
예를 들어
15 310 50 10 20 102 13 14 35 41
일 경우 제가 잘못 생각한 답안은
처음 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번 건물을 모두 지을 수 있습니다.
따라서 밑에는 다른 분이 남긴 예제였는데
15 510 20 30 40 501 21 32 43 45 44
답은 90이 나옵니다
댓글을 작성하려면 로그인해야 합니다.
wnsrl1228 2년 전 4
저는 건물을 짓는 도중에 다른 건물을 지을 수 없다고 생각하였습니다
(테스트 케이스는 위처럼 생각해도 답이 다 나왔음)
예를 들어
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이 나옵니다