2018년 정보올림피아드 지역예선 중등부 6~7번 고등부 1~2번 트리관련 문제 풀이

위의 문제는 단순히 계산을 해보면 되는 문제 입니다.

1번문제풀이)

총합을 최소로 하고자 한다면 다음과 같은 형태로 계산을 해 볼수가 있겠네요.

어차피 가운데로 몰릴 수 밖에 없으므로..

A -> B : 4

J -> I : 1

I -> H : 1 + 1 * 2 = 3 (J가 I 에 온 시간 1시간 + I 와 J가 H 로 이동하는 시간 1시간)

H -> E : 3 + 1 * 3 = 6 (J와 I가 H에 온시간 3시간 + I,J,H가 E로 이동하는 시간 3시간)

G -> E : 1

F -> E : 1

따라서 E까지 오는 하위 시장들의 모든 시간은 8 시간

B -> C : 4 + 1 * 2 = 6

C -> D : 6 + 1 * 3 = 9

D -> E : 9 + 1 * 4 = 13

E -> D : 8 + 1 * 6 = 14

따라서 D에 모일때는 왼쪽에서 모이는 시간 9 + 오른쪽에서 모이는 시간 14 = 23

E에서 모일때는 왼쪽에서 모이는 시간 13 + 오른쪽에서 모이는 시간 8 = 21

정답은 4번 E 입니다.

2번문제풀이) 

가장 빠른 시간은 가장 먼 거리에서 오는 시간을 계산 하면 됩니다

B는 왼쪽에서 A가 오는 시간 4 시간 오른쪽에서 J가 오는 시간 6시간 이므로 6시간이 걸립니다.

C는 왼쪽에서 A가 오는 시간 5시간 오른쪽에서 J가 오는 시간 5시간이므로 가장 짧은 시간이 됩니다.

정답은 2번 C 입니다.

정보올림피아드 문제 풀이 리스트 정리