[Python][백준] 10427번 빚

https://www.acmicpc.net/problem/10427

공부 날짜 : 2023.02.03
정답 참조 여부 : X

N번 돈을 빌렸는데, 사채업채의 빚 갚는 방식이 정말 이상하다.
사채 업채의 빚 갚는 방식에 맞춰(문제 참조) 1~N 별로 빚을 갚을때 갚아야 하는 빚을 최소값의 합을 출력하는 문제이다.

---

일단 빚을 빌린 순서가 중요하지 않았고, i번 무작위로 뽑을때 서로의 간격이 작아야 최소값을 구할 수 있기 때문에 정렬을 먼저 해줬다.

정렬은 처음에 list.sort()로 정렬을 해서 정답으로 나왔지만, 후에 버블정렬방식으로 내가 직접 한 정렬도 시간초과 없이 잘 정답으로 나왔다.

그 다음 정렬된 리스트를 기준으로 i크기의 구간합을 반복으로 구했다. 반환금액에서 구간합을 빼서 이자의 크기를 구했고, 그 이자를 반복하며 최소값을 찾은 뒤, answer변수에 값을 더해서 최종적인 답을 구했다.

---

항상 list.sort()메소드를 맹신하며 항상 사용해왔는데, 정렬 알고리즘도 어느정도 특징을 알 필요가 있을거 같아서 최근에 배운 버블정렬로 직접 풀어봤다. 시간 복잡도와 연산시간을 어느정도 계산할 수 있게 되었으니 앞으로 데이터 형식을 보고 정렬까지 직접 해보는 것도 괜찮겠다고 느꼈다.물론 기업 코테에선 메소드 써야지ㅋㅋ

소스코드

import sys
input = sys.stdin.readline
##############################################
def Sort(list_):
    for i in range(len(list_)):
        for j in range(len(list_) - i - 1):
            if list_[j] > list_[j+1]:
                list_[j], list_[j+1] = list_[j+1], list_[j]
##############################################

t = int(input())

for _ in range(t):
    n, *money = map(int, input().split())

    # 각 비용의 차이를 최소화 하기 위한 정렬
    Sort(money)

    answer = 0

    # S(1) ~ S(N)까지 구하기 위한 반복
    # S(1) ==  0 이므로 2부터 반복
    for i in range(2, n+1):
        sum_ = 0
        # 첫 0~i 까지 구간합
        for j in range(i):
            sum_ += money[j]
        min_value = money[i-1]*i - sum_

        # j~j+i 까지 구간합을 구해서 빚의 차이 계산후 최소값 갱신
        for j in range(i, n):
            sum_ = sum_ + money[j] - money[j-i]
            min_value = min_value if min_value < (money[j] * i) - sum_ else (money[j] * i) - sum_

        # S(i)의 최소값 더하기
        answer += min_value

    print(answer)