백준 1859번 파이썬 문제풀이(백만장자 프로젝트)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc 

SW Expert Academy

 

---

 

이 문제 이상하게 index 함수와 슬라이싱을 사용하면 10가지 출력이 모두 맞는데도 불구하고 런타임에러가 발생한다. 아마 숫자가 21억을 넘어가서 그런거 같다. (정확한 이유는 모르겠음..) 그래서 일반 for문으로 구성하니 정답이 출력되었다. 그리고 또한 반대로 탐색하며 마지막 인덱스를 최대값으로 설정하여 앞으로 탐색하면서 자신과 값의 차를 계속해서 더해준다. 그리고 만약 자신보다 높은 숫자가 나오면 그값을 최대값으로 하여 다시 앞으로 탐색한다. O(N)으로 시간최적화를 한 코드도 있다. 3가지 모두 제시하겠다.

 

1. for 문코드

import sys

sys.stdin = open('input.txt', 'r')


def solution():
    profit = 0
    start_index = 0
    max_index = 0
    max_ = 0
    now_buy_cost = 0
    count = 0
    while True:

        for i in range(start_index, N):
            if max_ < cost[i]:
                max_ = cost[i]
                max_index = i

        for i in range(start_index, max_index):
            now_buy_cost += cost[i]
            count += 1

        profit += (cost[max_index] * count) - now_buy_cost
        count = 0
        now_buy_cost = 0
        max_ = 0
        if max_index == len(cost) - 1:
            break

        start_index = max_index + 1

    return profit


T = int(input())

for order in range(1, 1 + T):
    N = int(input())
    cost = list(map(int, input().split()))

    print(f'#{order} {solution()} ')

 

2. 시간복잡도 최적화

import sys

sys.stdin = open('input.txt', 'r')


def solution():
    profit = 0

    max_ = cost[-1]
    for i in range(-2, -(1 + N), -1):
        if max_ < cost[i]:
            max_ = cost[i]
        else:
            profit += (max_ - cost[i])
    return profit


T = int(input())

for order in range(1, 1 + T):
    N = int(input())
    cost = list(map(int, input().split()))

    print(f'#{order} {solution()} ')

 

3. 슬라이싱 이용 (코드도 깔끔하고 정답도 맞게 출력되나 제출하면 런타임에러 발생)

import sys

sys.stdin = open('input.txt', 'r')


def solution():
    start_index = 0  # 시작 인덱스를 저장할 변수
    profit = 0  # 이익을 저장할 변수
    while True:
        max_ = max(cost[start_index:])  # 해당 시작인덱스 이후부터 최댓값 구하기
        max_index = cost.index(max_, start_index)  # 시작 인덱스 이후부터 존재하는 구간 중 그 최댓값의 인덱스를 구한다.

        now_buy_cost = sum(cost[start_index:max_index])  # 시작인덱스부터 최대인덱스 전까지의 누적 합을 구한다.
        count = max_index - start_index  # 그 구간 사이의 구매 개수를 구한다.

        # 이익 = (팔 금액 * 이때까지 구매했던 개수) - 내가 지금까지 구매한 금액
        profit += (cost[max_index] * count) - now_buy_cost

        # 만약 최대 인덱스가 마지막 인덱스라면 탈출
        if max_index == len(cost) - 1:
            break

        # 시작인덱스를 최대 인덱스 + 1 로 구해준다.
        start_index = max_index + 1

    return profit  # 이익 리턴


T = int(input())

for order in range(1, 1 + T):
    N = int(input())
    cost = list(map(int, input().split()))

    print(f'#{order} {solution()} ')