[240516] 코딩테스트 문제풀이

 

1. 주유소

• 거꾸로 풀면 안됨 ... 

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
del B[-1]
dp = [0] * n


for i in range(n) :
    if i == 0 :
        dp[-1] = A[-1] * B[-1]

    else :
        number = i * (-1)
        dp[number] = min((dp[number+1] + (A[number]*B[number])), B[number] * sum(A[number:]))

print(max(dp))

 

• 정답
  • for 문을 돌면서 비용 최솟값을 계속 업데이트 해주기 
  • 아 왜 이렇게 쉬운 로직을 자꾸 고민할까 ㅠㅠㅠ 

n = int(input())
A = list(map(int, input().split()))  # 도로의 길이
B = list(map(int, input().split()))  # 비용

c = B[0] # 초기비용
ans = 0

for i in range(n-1) :
    # 이전 비용 최솟값으로 -> 비용 계산
    if c > B[i] :
        c = B[i]
    ans += c * A[i]

print(ans)

 

---

2. 2+1 세일

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

• 도저히 이해가 안가는게 A[delete_index] = 0 이라고 설정해주면, 테스트가 통과가 안됨
• del A[delete_index] 을 해주고 index을 3씩 늘리는게 아니라 2씩 늘려야 함

import sys
input = sys.stdin.readline
n = int(input())
A = list()

for i in range(n) :
    A.append(int(input()))

count = len(A)
A.sort()

if count >= 3 :

    if count % 3 == 0 :
        delete_index = 0
        for i in range(count // 3) :
            del A[delete_index] 
            delete_index += 2


    elif count % 3 == 1 :
        delete_index = 1
        for i in range(count // 3) :
            del A[delete_index] 
            delete_index += 2

    else :
        delete_index = 2
        for i in range(count // 3) :
            del A[delete_index]
            delete_index += 2

print(sum(A))

 

---

3. 에너지 드링크

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

import heapq
from heapq import heapify

n = int(input())
A = list(map(int, input().split()))
heap = []

for i in range(len(A)) :
    heapq.heappush(heap, - A[i])

while len(heap) > 1 :
    number_one = heapq.heappop(heap)
    number_two = heapq.heappop(heap) / 2
    heapq.heappush(heap, number_one + number_two)

print(round(heap[0] * (-1),1))

 

---

4. 알바생 강호

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

n = int(input())
A = list()

# 입력받고, for 문 돌리기
for i in range(n) :
    A.append(int(input()))
A.sort(reverse = True)

answer = 0
for i in range(len(A)) :
    append_number = A[i] - i
    if append_number >= 0 :
        answer += append_number

print(answer)

 

---

5. 정렬하기

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

n = int(input())
A = list(map(int, input().split()))
A.sort()

answer = set()
if len(A) % 2 != 0 :
    answer.add(A[-1])
    del A[-1]

A.insert(0,0)
for i in range(1, len(A) // 2 + 1 ) :
    answer.add(A[i] + A[-i])

print(max(answer))

 

---

6.  주식

• 이렇게 마음대로 풀면 시간초과인거임 

import sys
input = sys.stdin.readline


N = int(input())

for i in range(N) :
    n = int(input())
    A = list(map(int, input().split()))
    answer = []
    count = 0

    while True :
        max_number = max(A)

        i = 0
        while A[i] != max_number :
            answer.append(A[i])
            del A[i]

        if len(answer) > 0 :
            for k in answer :
                count += (max_number - k )

        del A[0]
        answer = []

        if len(A) == 0 :
            break

    print(count)