
그리디 문제였다.
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로 제출하니 통과를 받았다.
예전에 한 번 봤던 문제였는데, 이제서야 풀었다.
'BOJ' 카테고리의 다른 글
백준(BOJ) 11003 최솟값 찾기(Python) (0) | 2022.07.09 |
---|---|
백준(BOJ) 18170 두 동전 언리미티드(Python) (0) | 2022.07.08 |
백준(BOJ) 1027 고층 건물(Python) (0) | 2022.07.08 |
백준(BOJ) 1799 비숍(Python) (0) | 2022.07.08 |
백준(BOJ) 1167 트리의 지름(Python) (0) | 2022.07.08 |