Coding 공부

import sys
input = sys.stdin.readline

T = int(input())

INF = 10**9
for _ in range(T):
    N = int(input())
    books = list(map(int,input().split()))
    prefix_sum = [0]*(N+1)
    dp =[[10**9] *N for _ in range(N)]
    min_k_store_array = list(range(N))
    for i in range(N):
        dp[i][i] = 0
        prefix_sum[i+1] = prefix_sum[i] + books[i]
    for term in range(1,N):
        new_arr = [None]*N
        for i in range(N-term):
            j = term+i
            for k in range(min_k_store_array[i],min(min_k_store_array[i+1]+1,j)):
                if dp[i][j] > dp[i][k]+dp[k+1][j]:
                    dp[i][j] = dp[i][k]+dp[k+1][j]
                    new_arr[i] = k

            dp[i][j] += prefix_sum[j+1] - prefix_sum[i]
        min_k_store_array = new_arr
    print(dp[0][N-1])

T = int(input())
INF = float('inf')

for _ in range(T):
    N = int(input())
    arr = list(map(int,input().split()))
    result = 0
    while len(arr) >=2:
        find_idx = len(arr)-2
        for i in range(len(arr)-2):
            if arr[i] <= arr[i+2]:
                find_idx = i
                break
        a1 = arr.pop(find_idx)
        a2 = arr.pop(find_idx)
        B = a1 + a2
        arr.insert(find_idx,B)
        result += B
        B_index = find_idx
        while B_index >0 and arr[B_index-1] < arr[B_index]:
            arr[B_index],arr[B_index-1] = arr[B_index-1],arr[B_index]
            B_index -= 1

    print(result)

import sys
import heapq
input = sys.stdin.readline


N,M = map(int,input().split())

dp = [-1]*100001
stack = []
dp[N] = 0
root_dict = {}
root_dict[N] = -1
heapq.heappush(stack,(0,N))
if N == M:
    print(0)
    print(N)
else:
    flag = False
    while stack:
        cnt, x = heapq.heappop(stack)
        for ind,nx in enumerate([2*x,x-1,x+1]):
            if 0<=nx<100001:
                if dp[nx] == -1:
                    dp[nx] = cnt + 1
                    root_dict[nx] = x
                    heapq.heappush(stack,(cnt+1,nx))
                    if nx == M:
                        find_route = [nx]
                        cu_route = nx
                        while cu_route != N:
                            cu_route = root_dict[cu_route]
                            find_route.append(cu_route)
                        flag = True
                        print(cnt+1)
                        print(*reversed(find_route))
                        break
        if flag:
            break

import sys
from collections import deque
input = sys.stdin.readline


N,M = map(int,input().split())

dp = [-1]*100001
stack = deque()
dp[N] = 0
root_list = [-1]*100001
stack.append((0,N))
if N > M:
    print(N-M)
    print(' '.join(map(str,range(N,M-1,-1))))
elif N == M:
    print(0)
    print(N)
else:
    flag = False
    while stack:
        cnt, x = stack.popleft()
        for ind,nx in enumerate([2*x,x-1,x+1]):
            if 0<=nx<100001:
                if dp[nx] == -1:
                    dp[nx] = cnt + 1
                    root_list[nx] = x
                    stack.append((cnt+1,nx))
                    if nx == M:
                        find_route = [nx]
                        cu_route = nx
                        while cu_route != N:
                            cu_route = root_list[cu_route]
                            find_route.append(cu_route)
                        flag = True
                        print(cnt+1)
                        print(*reversed(find_route))
                        break
        if flag:
            break

from collections import deque

def roll(direction,red,blue):
    global arr,visited
    stack = deque()
    red = [*red,True]
    blue = [*blue,True]
    stack.append((red,blue))
    while stack:
        r,b = stack.popleft()

        r_x,r_y,r_state = r
        b_x,b_y,b_state = b
        visited[r_x][r_y] = False
        if r_state:
            nr_x = r_x + dx[direction]
            nr_y = r_y + dy[direction]
            if 0<=nr_x<N and 0<=nr_y<M:
                if nr_x == b_x and nr_y == b_y:
                    if not b_state:
                        r_state = False
                else:
                    if arr[nr_x][nr_y] == '#':
                        r_state = False
                    elif arr[nr_x][nr_y] == 'O':
                        r_state = False
                        r_x = -1
                        r_y = -1
                    else:
                        r_x = nr_x
                        r_y = nr_y
        if b_state:
            nb_x = b_x + dx[direction]
            nb_y = b_y + dy[direction]
            if 0<=nb_x<N and 0<=nb_y<M:
                if nb_x == r_x and nb_y == r_y:
                    if not r_state:
                        b_state = False
                else:
                    if arr[nb_x][nb_y] == '#':
                        b_state = False
                    elif arr[nb_x][nb_y] == 'O':
                        b_state = False
                        b_x = -1
                        b_y = -1
                    else:
                        b_x = nb_x
                        b_y = nb_y
        
        if not r_state and not b_state:
            if b_x == -1:
                return -1
            if r_x == -1:
                return 1
            return [r_x,r_y,b_x,b_y]
        
        stack.append(([r_x,r_y,r_state],[b_x,b_y,b_state]))


def bfs(r,b,g):
    global arr
    stack = deque()
    stack.append((r,b,0))
    visited[r[0]][r[1]] = False
    while stack:
        red,blue,cnt = stack.popleft()
        if cnt >= 10:
            return -1
        for i in range(4):
            nx = red[0] + dx[i]
            ny = red[1] + dy[i]
            if 0<=nx<N and 0<=ny<M:
                result = roll(i,red,blue)
                if type(result) == int:
                    if result == 1:
                        return cnt+1
                else:
                    nr = [result[0],result[1]]
                    nb = [result[2],result[3]]
                    stack.append((nr,nb,cnt+1))
    return -1
dx = [-1,1,0,0]
dy = [0,0,-1,1]


N,M = map(int,input().split())

arr = []
red_ball = []
blue_ball = []
goal = []
visited = [[True]*M for _ in range(N)]
for x in range(N):
    temp = list(input())

    for y in range(M):
        if temp[y] == 'R':
            temp[y] = '.'
            red_ball = [x,y]
        elif temp[y] == 'B':
            temp[y] = '.'
            blue_ball = [x,y]
        elif temp[y] == 'O':
            goal = [x,y]
    arr.append(temp)
print(bfs(red_ball,blue_ball,goal))

N = int(input())
arr = list(map(int,input().split()))

B,C = map(int,input().split())
answer = 0
for num in arr:
    num -= B
    answer += 1
    if num > 0:
        answer = answer + num//C + (0 if num%C == 0 else 1)
print(answer)

import heapq
def check(D):
    global result
    possible_set = []

    while rail_list:
        END,START = heapq.heappop(rail_list)
        if END-D <=START:
            heapq.heappush(possible_set,START)
        while possible_set and possible_set[0] < END-D:
            heapq.heappop(possible_set)
        
        result = max(result,len(possible_set))




N = int(input())
rail_list = []
for idx in range(N):
    A,B = map(int,input().split())
    if A > B:
        A,B = B,A
    heapq.heappush(rail_list,(B,A))

d = int(input())
result = 0
check(d)
print(result)

import heapq

N = int(input())
rail_list = []
for idx in range(N):
    A,B = map(int,input().split())
    if A > B:
        A,B = B,A
    rail_list.append((A,B))
rail_list.sort(key=lambda x : x[1])

in_rail = []
d = int(input())
result = 0
for start,end in rail_list:
    if end-d <= start:
        heapq.heappush(in_rail,start)
    while in_rail and end-d > in_rail[0]:
        heapq.heappop(in_rail)
    result = max(result,len(in_rail))
print(result)

N, M  = map(int,input().split())
not_visited_days = [True]*(N+1)
if M:
    for k in list(map(int,input().split())):
        not_visited_days[k] = False
        

INF = float('inf')
dp = [[INF for _ in range(40)] for _ in range(105)] 

dp[0][0] = 0


for day in range(N):
    for coupon in range(37):
        if not not_visited_days[day+1]:
            dp[day+1][coupon] = min(dp[day+1][coupon],dp[day][coupon])
        dp[day+1][coupon] = min(dp[day+1][coupon],dp[day][coupon] + 10000)
        dp[day+3][coupon+1] = min(dp[day+3][coupon+1],dp[day][coupon] + 25000)
        dp[day+5][coupon+2] = min(dp[day+5][coupon+2],dp[day][coupon] + 37000)

    for coupon in range(39,2,-1):
        dp[day+1][coupon-3] = min(dp[day+1][coupon-3],dp[day][coupon])
    

print(min(dp[N]))
    
    
    

N,K = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
diff = [0]*N
for i in range(N-1):
    diff[i] = arr[i+1] - arr[i]

diff.sort()
print(sum(diff[:len(diff)-(K-1)]))

import heapq
import sys

def dijkstra(S,E,TERM):
    INF = float('inf')
    distance_list = [INF]*(N+1)
    distance_list[S] = TERM
    node_list = []
    heapq.heappush(node_list,(TERM,S))

    while node_list:
        cur_time,cur_node = heapq.heappop(node_list)

        for next_node in graph[cur_node]:
            if time_spend_list.get((cur_node,next_node)) and time_spend_list[(cur_node,next_node)][0]<=cur_time<=time_spend_list[(cur_node,next_node)][1]:
                spend_time = time_spend_list[(cur_node,next_node)][1] + graph[cur_node][next_node]
            else:
                spend_time = cur_time + graph[cur_node][next_node]
            
            if distance_list[next_node] > spend_time:
                distance_list[next_node] = spend_time
                heapq.heappush(node_list,(spend_time,next_node))

    return distance_list


input = sys.stdin.readline

N,M = map(int,input().split())

start_point,end_point,king_term,G = map(int,input().split())

king_visit_list = list(map(int,input().split()))


graph = [{} for _ in range(N+1)]

for _ in range(M):
    x,y,times = map(int,input().split())

    graph[x][y] = min(graph[x].get(y,float('inf')),times)
    graph[y][x] = min(graph[y].get(x,float('inf')),times)



time_spend_list = {}

king_time = 0
for ind in range(G-1):
    start,ends = king_visit_list[ind],king_visit_list[ind+1]
    time_spend_list[(start,ends)] = (king_time,king_time+graph[start][ends])
    time_spend_list[(ends,start)] = (king_time,king_time+graph[start][ends])
    king_time += graph[start][ends]


result = dijkstra(start_point,end_point,king_term)


print(result[end_point]-king_term)