백준 25426번 - 일차함수들

1. 문제 난이도

---

2. 문제설명

일차함수가 $n$개 있다.

$f_{i} (x) = a_{i} x + b_{i}$ 처럼 표현한다.

이 함수들의 $x$부분에 각각  $1$부터 $n$까지 한번씩 대입해 만들 수 있는

$f(x)$의 최댓값을 구하는 문제이다.

<INPUT>

첫번째 줄: $n$

두번째 줄부터 $n$개의 줄에 걸쳐

$a_{i}, b_{i}$가 공백으로 구분되어 입력

 

<OUTPUT>

최댓값

---

 

3. 아이디어

문제에서 변할 수 있는 부분은 $x$와 곱해지는 $a$부분이다.

반대로 얘기하면 $b$는 변하지 않는다는 것이다.

 

그래서 $b$부분은 먼저 최댓값에 더하기로 했다.

 

이제 $b$를 빼고 생각하면 되므로 $ax$부분의 최댓값을 구하면 된다.

$x$는 $1$부터 $n$까지 한번씩만 사용되므로

큰 $a$값과 큰 $x$값이 서로 곱해지는게 최댓값이 된다.

 

그래서 $a$들을 크기순으로 나열하고

각각 $1$부터 $n$까지 곱하는 방식을 사용하기로 했다.

---

4. 구현

input의 개수가 많아질 수 있으므로

sys를 import해서 sys.stdin.readline()을 사용해주었다.

 

lista

$a_{i}$들을 담을 리스트

lista.sort()를 사용해 크기순으로 정렬해주었다.

 

sumb

초반은 $b_{i}$들의 합을 저장하고

후에 $a_{i}$와 $x$의 곱들을 더하는 변수이다.

import sys

n=int(input())
lista=[]
sumb=0
for i in range(n):
    a,b=map(int, sys.stdin.readline().split())
    lista.append(a)
    sumb=sumb+b

lista.sort()
for j in range(1,n+1):
    sumb=sumb+lista[j-1]*j

print(sumb)

댓글, 오류지적 모두 감사합니다