0. 서문

오늘로써 알고리즘 4주차 시험을 끝으로 공싱적으로 정글에서 진행하는 알고리즘은 끝을 내리게 되었다.

그렇다고 하더라도 나를 포함해서 대부분 스터디 혹은 개인적으로라도 알고리즘을 이어나갈 생각들인것같다. 역시 어느정도 규모있는 회사로 갈려면 알고리즘은 필수인지라...

4주차를 마치면서 느끼는 회고는 따로 작성하려한다.

추가로 이제 5주차에 접어들면서 C언어를 배우게 되어서 C언어 TIL 도 해볼까 한다.

AKMU - DINOSAUR

1. 계단오르기

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

이전에도 푼적있었던 문제였는데 우연히 문제로 나왔다. 이래서 알고리즘 문제는 일단 많이 풀어야하는것같다

import sys
input = sys.stdin.readline

n = int(input())
stair = [0] + [int(input()) for _ in range(n)]

if n == 1:
    print(stair[1])
else:
    dp = [0] * (n+1)
    dp[1] = stair[1]
    dp[2] = stair[1] + stair[2]

    for i in range(3, n+1):
        dp[i] = max(dp[i-3]+stair[i-1]+stair[i], dp[i-2]+stair[i])

    print(dp[n])

2. 보석 도둑

이것도 이전에 한번 풀어봤었던 문제 우연히 3문제중 2문제가 이전에 풀어봤던 문제라 이번 시험은 비교적 쉽게 볼 수 있었다. 같은 조 조원은 추가로 한문제도 이전에 풀어봤다더라.

import heapq
import sys

n, m = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(n)]
pack = [int(input()) for _ in range(m)]
arr.sort()
pack.sort()

result = 0
temp = []

for i in pack:
    while arr and i >= arr[0][0]:
        heapq.heappush(temp, -arr[0][1])
        heapq.heappop(arr)

    if temp:
        result += heapq.heappop(temp)
    elif not arr:
        break

print(-result)

3. ATM

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

그리디 분류쪽 문제중 기초쯤에 해당하는것들을 다 풀어볼려고 푼 문제. 근데 DP 에 가깝게 푼것같기도 하다. 그리디 방식이라서 직관적으로 보자마자 푸는 방법이 보였던지라 운좋게 바로 맞출 수 있었다.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
dp = [0] * (n)
dp[0] = arr[0]
result = 0

for i in range(1, n):
    dp[i] = dp[i-1] + arr[i]


print(sum(dp))

4. 주식

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

주어진 값을 반대로 계산해서 마지막날 ~ 첫번째 날 순서로 계산하는 방식으로 진행하였다.

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
    t = int(input())
    arr = list(map(int, input().split()))
    arr.reverse()
    value = 0
    maximum = 0

    for i in arr:
        if i > maximum:
            maximum = i
        else:
            value += maximum - i
    print(value)