[Greedy] 백준 4307번 “개미” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/4307

풀이

• "두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다."
  • 해당 문구는 전혀 고려하지 않아도 되는 문제입니다.
• 예를 들어, 길이 10의 막대기가 있고, 개미 3마리가 순서대로 2, 6, 7의 위치에 존재한다면,
• 각 개미가 땅으로 떨어지는 최소 시간과 최대 시간은 아래와 같습니다.
  • 개미 1
    • 최소 : 2, 최대 : 8
  • 개미 2
    • 최소 : 4, 최대 : 6
  • 개미 3
    • 최소 : 3, 최대 : 7
• 모든 개미가 땅으로 떨어지는 최소 시간과 최대 시간을 구하는 문제이므로,
• 각 개미가 땅으로 떨어지는 최소 시간 중 제일 큰 값은 4,
• 각 개미가 땅으로 떨어지는 최대 시간 중 제일 큰 값은 8이므로,
• 주어진 예제의 정답과 같게 됩니다.

코드

import sys

# 테스트 케이스의 개수
t = int(sys.stdin.readline())

for _ in range(t):

    # 막대의 길이와 개미의 수
    stick_len, ant_count = map(int, sys.stdin.readline().split())

    # 최소 시간 배열
    min_time = []

    # 최대 시간 배열
    max_time = []

    # 개미의 위치
    for _ in range(ant_count):

        # 현재 개미의 위치
        loc = int(sys.stdin.readline())

        # 현재 개미가 땅으로 떨어지는 최소 시간 저장
        min_time.append(min(loc, stick_len - loc))

        # 현재 개미가 땅으로 떨어지는 최대 시간 저장
        max_time.append(max(loc, stick_len - loc))

    # 각 개미가 땅으로 떨어지는 최소 시간 중 제일 큰 값과
    # 각 개미가 땅으로 떨어지는 최대 시간 중 제일 큰 값을 출력
    print(max(min_time), max(max_time))

참고

• https://pangsblog.tistory.com/22