백준 4307번: 개미

[www.acmicpc.net/problem/4307]

#풀이

- 그리디 알고리즘

개미가 만나는 순간에서 어떻게 계산해야 할지 고민을 했을 것이다.

개미가 부딪힐때 만나는 개미는 해당개미의 속도와 방향을 계승하므로 만날 때를 고려하지 않아도 된다. 

예를 들면 다음과 같은 상황이 있다.

만나는 것을 고려했을 때 상황을 그림으로 나타내었다.

이것을 만나는 것을 고려하지 않았을 때의 T = 2 와 비교해보자. 비교해보면 둘의 상황은 같다고 나올 것이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

import sys   num=int(sys.stdin.readline()) for _ in range (num):     ma,mi=0,0     leng,ant=map(int,sys.stdin.readline().split())     for _ in range(ant):         num=int(sys.stdin.readline())         x,n=max(num,leng-num),min(num,leng-num)         if mi<n:             mi=n         if ma<x:             ma=x     print(mi,ma) Colored by Color Scripter

cs