백준(BOJ) 2180 소방서의 고민(Python)

 

 

문제 내용

 

그리디 문제였다.

at+b 꼴의 일차 함수에서 단순히 a와 b값만으로 정렬해서 문제를 풀 수 없다고 생각했고, 느낌상 b/a로 정렬하면 될 것이라고 생각했다.

그러나 확신이 없어서 결국 검색해보니 내 감이 맞았다.

당연히 b/a 값이 같다면 a값이 더 큰 순으로 정렬해야 더 효율적이기 때문에 key는 b/a, -a 순으로 오름차순 정렬했다.

그러나 여기서 문제는 a가 0인 경우 어떻게 할 것인가인데, a가 0인 경우에는 t에 상관없이 진화 시간이 똑같으므로 b의 크기에 관계 없이 우선 순위의 맨 뒤에 위치해야한다. 따라서 b/a 자리에 INF를 넣어주면서 알고리즘을 완성시켰다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
L=[]
inf=10e9
for i in range(n):
    a,b=map(int,input().split())
    if a==0:
        L.append([a,b,inf])
    else:
        L.append([a,b,b/a])
L.sort(key=lambda x:(x[2],x[0]))
ans=0
t=0
for i in L:
    a,b,c=i
    ans+=a*ans+b
    ans%=40000
print(ans)

 

 

계산 횟수가 많아서 python으로는 시간 초과가 터졌다.

그래서 pypy로 제출하니 통과를 받았다.

예전에 한 번 봤던 문제였는데, 이제서야 풀었다.