소공전 timer 1s memory 128MB

정올에서는 올해 학생들의 의욕을 고취시키기 위해 이번 달에 소프트웨어 공모전(일명 소공전)을 개최하기로 하였다. 

그래서, 많은 학생들은 소공전에 입상하기 위하여 지단 몇 달 동안 밤새 프로젝트에 몰두하곤 한다.

철기도 이번 소공전에 참가하려는 학생 중 한 명이다. 

허나, 철기는 오늘까지 아무런 준비를 안하고 보낸 덕분에, 소공전 준비를 전혀 하지 못했다.

시간이 얼마 남지 않았기 때문에, 철기는 어떻게 하면 프로젝트를 빨리 완성할 수 있을지 연구하기 시작 하였고, 

그 결과, 프로젝트를 여러 개의 작은 작업(task)으로 나누어서 진행하면 더 효과적일 것이라는 결론을 내렸다.

프로젝트를 여러 개의 작업으로 나누고, 각 작업들의 흐름도(flowchart)를 그려본 후, 

어떤 작업들은 서로 의존성이 없어서 동시에 진행할 수 있지만,

어떤 작업들은 다른 작업들이 끝나야 시작할 수 있음을 알았다. 

철기는 작업 흐름도를 완성한 후, 프로젝트가 몇 일만에 끝날 수 있을지 계산해 보려고 한다. 

과연 철기는 몇 일만에 프로젝트를 완성할 수 있을까?

여기서 다음과 같은 조건을 항상 만족한다고 가정한다. 1) 모든 작업들은 마치는데 균일하게 하루가 걸린다. 2) 철기의 프로젝트를 도울 수 있는 친구들이 무한이 많다. 

따라서 서로 의존성이 없는 작업들은 모두 동시에 진행할 수 있다 3) 작업간의 의존성이 cycle을 이루지 않는다. 

예를 들어, A B, B C, C A 와 같은 경우는 없다. (A B는 작업 B를 시작하기 위해서는 작업 A가 먼저 끝나야 한다는 의미이다.)

예를 들어, A, B, C, D, E, F, G라는 작업들이 아래 그림과 같은 의존성을 가지고 있다고 하자.

   D라는 작업을 시작하기 위해서는 B와 C작업을 먼저 끝내야 한다. 

C작업을 시작하기 위해서는 A, B, E작업을 끝내야 하고, B작업을 시작하기 위해서는 A작업을 끝내야 한다. 

그러나, A와 E나 F같은 경우는 서로 의존성이 없으므로 동시에 수행할 수 있다.

위와 같은 경우,

첫째 날 (A, E, F)를 수행하고, 

둘째 날 (B, G)를 수행하고, 

셋째 날 (C)를 수행하고, 

넷째 날 (D)를 수행할 수 있다. 

따라서 4일 만에 프로젝트를 완성할 수 있다.