Coding 공부

import sys
import math
def input():
    return sys.stdin.readline().rstrip()
 
def check(max_hp):
    cu_atk = input_atk
    cu_hp = max_hp
    for command,atk,hp in arr:
        if command == 1:
            atk_cnt = math.ceil(hp/cu_atk)
            cu_hp -= (atk_cnt-1)*atk
            if cu_hp<=0:
                return False
        else:
            cu_atk += atk
            cu_hp += hp
            if cu_hp> max_hp:
                cu_hp = max_hp
    return True
 
N,input_atk = map(int,input().split())
 
arr = []
 
 
for _ in range(N):
    t,a,h = map(int,input().split())
 
    arr.append((t,a,h))
 
left = 0
right = 999999000001*123456
 
 
while left+1<right:
    mid = (left+right)//2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)

첫 풀이는 전형적인 이분탐색 풀이이다.

올림을 통해 적 hp를 현재 용사의 공격력으로 나눈 몫을 올림을 해서 용사의 공격횟수를 구했다.

그리고 마지막 공격으로 적이 죽었을때에는 공격을 맞지 않으므로, 용사의 공격횟수에서 -1을 하고

몬스터의 공격력 만큼 곱해서 용사의 hp를 줄여준다.

이때 0보다 이하이면, False를 반환해준다.

그리고 물약이 있는곳이 생기면 용사의 공격력을 올려주고, 설정된 최대피를 넘어가게 회복되면 최대피로 바꿔주면 된다.

이런식으로 해서 용사가 죽지않고 던전을 돌파할 수 있는 최소 피를 구하면 된다.

import sys
import math
def input():
    return sys.stdin.readline()
 
 
N,user_atk = map(int,input().split())
 
 
max_hp = 0
acc_hp = 0
# 데미지는 마이너스
# 힐은 플러스
damage_or_heal = 0
 
 
arr = [list(map(int,input().split())) for _ in range(N)]
 
 
for command,atk,hp in arr:
    if command == 1:
        atk_cnt = math.ceil(hp/user_atk)
        damage_or_heal = -(atk_cnt-1)*atk
    else:
        user_atk += atk
        damage_or_heal = hp
    
    acc_hp += damage_or_heal
    if acc_hp>0:
        acc_hp = 0
    max_hp = max(max_hp,abs(acc_hp))
print(max_hp+1)

 두번째 풀이는 신박한 풀이였다.

최대 누적 데미지를 계산을 해서 푸는 방식이였다.

이 방식은 단 한번의 반복문으로 구할 수 있으므로, 윗 방식보다 더 빠른 방식이다.

최대 누적데미지를 구하는 방식은 다음과 같다.

damage_or_heal은 용사가 받은 데미지나 heal을 나타내는 것이다.

데미지이면 마이너스값을 받고, heal이면 플러스 값을 받는다.

max_hp는 우리가 구할 최대 hp이다.

acc_hp는 현재까지 누적된 데미지라고 생각하면 된다.

damage_or_heal은 위에서 구한 것처럼 몬스터의 공격데미지와 힐을 구해서 만들어주면 된다.

여기서 중요한것은 acc_hp에 이 값을 더해주는 것이다.

이 값이 0보다 크게 되면 용사는 지금까지누적된 데미지를 넘어서 회복을 하게 된것 이므로 과다힐이 된것이다.

그래서 acc_hp 값이 0보다 크게 되면 0으로 초기화를 시켜준다.

그리고 acc_hp가 -이면 현재턴에서 용사가 딱 죽을 hp이다. 

즉 용사가 acc_hp의 절대값만큼의 hp를 가지고 있으면 이 해당턴에서 딱 0이 되어서 죽는것이다.

우리는 이 acc_hp의 절대값과 max_hp와 최대값을 계속 비교를 해서,

각 턴마다, 용사가 받는 최대 데미지를 구해준다.

이렇게 구한 max_hp를 가지고 용사가 던전에 들어가게 되면 중간에 피가 0이되어 죽으므로, 이 값보다 딱 1을 높게 해주면,

용사는 던전을 탐험하는 도중 받을수 있는 해당 턴의 누적데미지보다 hp가 크므로 죽지않고 던전을 돌파할 수 있게 된다.

이분 탐색이 아닌 방식으로도 풀 수 있는 것이었다.

import sys
sys.setrecursionlimit(100000)
def input():
    return sys.stdin.readline()
 
def dfs(node,d):
    visited[node] = False
    depth[node] = d
    for next_node in tree[node]:
        if not visited[next_node]:
            continue
        parents[next_node][0] = node
        dfs(next_node,d+1)
 
 
 
def LCA(X,Y):
    if depth[X] != depth[Y]:
        if depth[X]>depth[Y]:
            X,Y = Y,X
        for i in range(MAX_NODE-1,-1,-1):
            if (depth[Y]-depth[X] >= (1<<i)):
                Y = parents[Y][i]
    if X == Y:
        return X
    if (Y != X):
        for i in range(MAX_NODE-1,-1,-1):
            if parents[X][i] != parents[Y][i]:
                X = parents[X][i]
                Y = parents[Y][i]
    return parents[X][0]
N = int(input())
MAX_NODE = 17
tree = [[] for _ in range(N+1)]
parents =  [[0 for _ in range(MAX_NODE)] for _ in range(N+1)]
depth = [0 for _ in range(N+1)]
for i in range(N-1):
    x,y = map(int,input().split())
    tree[y].append(x)
    tree[x].append(y)
 
M = int(input())
visited = [True for _ in range(N+1)]
dfs(1,0)
 
 
for y in range(1,MAX_NODE):
    for x in range(1,N+1):
        parents[x][y] = parents[parents[x][y-1]][y-1]
 
for _ in range(M):
    x,y = map(int,input().split())
    print(LCA(x,y))

사과나무에서 썼던 LCA 공식을 그대로 가져와서 썼다.

여전히 잘 외워지지는 않는다.

나중에 LCA를 공부할때 다시 공부해서 이 유형을 다시 공부해야겠다.

import sys
 
def input():
    return sys.stdin.readline()
 
N = int(input())
INF = float('inf')
dp = [INF for _ in range(101)]
dp[2] = 1
dp[3] = 7
dp[4] = 4
dp[5] = 2
dp[6] = 6
dp[7] = 8
dp[8] = 10
 
for num in range(9,101):
    for i in range(2,8):
        if i != 6:
            dp[num] = min(dp[num],dp[num-i]*10+dp[i])
        else:
            dp[num] = min(dp[num],dp[num-i]*10)
for _ in range(N):
    k = int(input())
    
    max_value = ('7' if k%2 else '1' ) +'1'*(k//2-1)
    print(dp[k],max_value)

이 문제를 푸는 방식은 다음과 같다.

2개부터 8개까지의 성냥개비를 이용해서 만들 수 있는 최소의 수가 있다.

먼저 이 수들을 각각 저장을 해주는 것이다.

단 여기서 주의해야할 점은 성냥개비의 개수가 6개일때다.

6개일때는 원래 최저의 수는 0이지만, 자리수가 1개일때 0이 올수가 없다. 이 점만 주의해주면 된다.

이렇게 2~8개의 최소 숫자를 구해주고

9개부터는 그리디하게 찾아주면 된다.

dp [ 현재 성냥의 개수 - i개 ] *10 + dp[i] 와 dp[현재 성냥의 개수] 의 최소값을 비교해서 갱신해주면 된다.

그리고 위에 말했듯이 6개일때는 가장 작은 수는 0 이므로 *10만 해주면 된다.

이렇게 최소 숫자를 구했으면,

최대 숫자를 구해야한다.

여기서 가장 큰 숫자를 만드는 법은 가장 적은 개수로 만들수 있는 1로 채우는 것이다.

그런데 이럴때 문제는 성냥의 개수가 홀수일때 문제가 된다.

성냥의 개수가 홀 수 일때 1개가 남아서, 어떠한 숫자도 만들수 없다.

그러므로 주어진 성냥개비의 숫자가 홀수이면, 가장 앞의 수를 1이 아닌 성냥개비 3개로 만들수 있는 가장 큰수를 만들어줘야한다.

그에 부합하는 숫자는 7 이므로,

주어진 성냥 개비의 숫자가 홀수이면 7 아니면 1을 붙이고, 성냥개비를 2로 나눈 몫에서 1을 뺀숫자만큼 붙여주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
def make_group(limit):
    temp = 0
    cnt = 0
    result = []
    group_cnt = K
    for ind in range(N):
        temp += arr[ind]
        if temp>limit:
            temp = arr[ind]
            result.append(cnt)
            group_cnt -= 1
            cnt = 0
        cnt += 1
        if group_cnt == (N-ind):
            result.append(cnt)
            group_cnt -= 1
            while group_cnt:
                result.append(1)
                group_cnt -= 1
            return result
 
def count_group(val):
    k = 0
    temp = 0
    for ind in range(N):
        temp += arr[ind]
        if temp>val:
            temp = arr[ind]
            k += 1
    if temp:
        k += 1
    return k
 
 
N,K = map(int,input().split())
 
arr = list(map(int,input().split())) 
 
 
left = max(arr)-1
right = sum(arr)
answer = right
while left+1<right:
    mid = (left+right)//2
    K_mid = count_group(mid)
    if K_mid > K:
        left = mid
    else:
        right = mid
print(right)
print(*make_group(right))

최근 풀었던 문제들 중에서 가장 어렵게 푼 문제였다.

이 문제는 단순한 이분탐색으로 끝나는 것이 아닌, 그룹을 구하는게 힘들었다.

그룹을 만드는 방식은 다음과 같다.

문제에 주어진 M개의 그룹을 강제적으로 만들어줘야한다.

즉 우리가 그룹을 만들어야하는 개수와 현재 남은 구슬의 수가 동일하다면,

나머지 구슬들을 전부 1개씩으로 만들어줘야한다.

이 점을 주의해서 풀어주면 문제를 해결할 수 있는 문제였다.

import sys
import heapq
 
def dijkstra(flag=False,*arg):
    distance = [INF for _ in range(N+1)]
    distance[1] = 0
    node_list = []
    if flag:
        remove_node = arg[0]
    heapq.heappush(node_list,(0,1))
    
    while node_list:
        cur_dis,node = heapq.heappop(node_list)
        if cur_dis>distance[node]:
            continue
        for next_node in graph[node]:
            if flag and ((node,next_node) == remove_node or (next_node,node) == remove_node):
                continue 
            temp_distance = cur_dis + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    if not flag:
        stack = [(N,distance[N])]
        while stack:
            node,dis = stack.pop()
            for prev_node in graph[node]:
                if (prev_node,node) not in short_list:
                    if distance[prev_node] + graph[prev_node][node] == dis:
                        short_list.add((prev_node,node))
                        stack.append((prev_node,distance[prev_node]))
 
    return distance[N]
    
 
def input():
    return sys.stdin.readline()
 
 
N,M = map(int,input().split())
 
graph = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay
 
INF = float('inf')
 
short_list = set()
short_time = dijkstra()
short_list = list(short_list)
 
result = -1
for node in short_list:
    remove_time = dijkstra(True,node)
    result = max(result,remove_time - short_time)
 
print(result if result != INF else -1)

문제를 푸는 방식은 다음과 같다.

먼저 다익스트라로 최단 거리를 구한다.

그와 동시에 이동경로를 구해야한다.

즉 우리는 다익스트라를 하면서 누적된 이동거리 리스트를 이용해서 역산을 통해 최단 거리의 이동 경로를 구한다.

이렇게 구한 이동경로를 하나씩 검문을 하는 것이다.

그리고 그 검문을 했을때의 다익스트라를 구하고, 이 때의 최대값을 구하고, 지연된 시간을 구하면 된다.

이 문제는 다익스트라를 통해 이동경로를 추적하고, 그 이동경로를 활용해서 풀 수 있는 문제였다.

import sys
from collections import defaultdict
import heapq
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())
 
 
 
graph = [defaultdict(list) for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y].append((pay,True))
    graph[y][x].append((pay,False))
 
 
node_list = []
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
distance_list[1] = 0
heapq.heappush(node_list,(0,1,1,True))
result = []
 
while node_list:
    cur_dis, cur_node , parent_node , cur_flag = heapq.heappop(node_list)
    if cur_dis > distance_list[cur_node]:
        continue
    if cur_node != parent_node:
        if cur_flag:
            result.append((parent_node, cur_node))
        else:
            result.append((cur_node, parent_node))
    for next_node in graph[cur_node]:
 
 
        for pay,flag in graph[cur_node][next_node]:
            if cur_dis + pay < distance_list[next_node]:
                distance_list[next_node] = cur_dis + pay
                heapq.heappush(node_list,(distance_list[next_node], next_node , cur_node , flag))
    
print(len(result))
for row in result:
    print(*row)

처음으로 풀었던 방식이다. 문제의 출력을 입력에 주어진 간선으로 출력해야하는 줄 알고, 좀 복잡하게 풀었다.

이 문제를 처음 본 순간 MST 문제 인줄 알았는데, MST 문제는 아니였다.

1번 조건만 보고 모든 노드들이 연결되는 최소인줄 알고 MST인줄 알았는데,

2번 조건을 찬찬히 읽어보니 다익스트라 문제였다.

네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

그 2번 조건은 다음과 같다.

슈퍼컴퓨터를 기준으로 모든 컴퓨터들은 최소 시간을 보장해야한다.

즉 슈퍼컴퓨터를 기준으로 모든 노드들에 대한 최소 시간의 다익스트라를 구해야하는 문제이다.

이 점만 주의하면 일반적인 다익스트라 풀이와 동일하다.

import sys
from collections import defaultdict
import heapq
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())
 
 
 
graph = [defaultdict(list) for _ in range(N+1)]
 
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y].append(pay)
    graph[y][x].append(pay)
 
 
node_list = []
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
distance_list[1] = 0
heapq.heappush(node_list,(0,1,1))
result = []
 
while node_list:
    cur_dis, cur_node , parent_node  = heapq.heappop(node_list)
    if cur_dis > distance_list[cur_node]:
        continue
    if cur_node != parent_node:
        result.append((parent_node, cur_node))
    for next_node in graph[cur_node]:
 
 
        for pay in graph[cur_node][next_node]:
            if cur_dis + pay < distance_list[next_node]:
                distance_list[next_node] = cur_dis + pay
                heapq.heappush(node_list,(distance_list[next_node], next_node , cur_node ))
 
print(len(result))
 
for row in result:
    print(*row)

개선한 풀이이다.

import sys
import heapq
from collections import deque
def input():
    return sys.stdin.readline()
 
N,M = map(int,input().split())
 
arr = [list(input()) for _ in range(N)]
 
start = [0,0,0]
node_list = []
total_cnt = 0
for x in range(N):
    for y in range(N):
        if arr[x][y] == 'S':
            start = [0,x,y]
            arr[x][y] = '0'
 
 
 
heapq.heappush(node_list,start)
INF = float('inf')
visited = [[True for _ in range(N)] for _ in range(N)]
distance = [[INF for _ in range(N)] for _ in range(N)]
result = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
cnt = 0
while node_list:
    cur_dis,x,y, = heapq.heappop(node_list)
    if not visited[x][y]:
        continue
    if cur_dis > distance[x][y]:
        continue
    result += cur_dis
    cnt += 1
    visited[x][y] = False
 
    temp_visited = [[True for _ in range(N)] for _ in range(N)]
    queue = deque()
    queue.append((x,y,0))
    temp_visited[x][y] = False
    while queue:
        qx,qy,dis = queue.popleft()
 
        for i in range(4):
            nx = qx + dx[i]
            ny = qy + dy[i]
 
            if temp_visited[nx][ny] and arr[nx][ny] != '1':
                temp_visited[nx][ny] = False
                queue.append((nx,ny,dis+1))
                if arr[nx][ny] == 'K' and distance[nx][ny] > dis+1:
                    distance[nx][ny] = dis + 1
                    heapq.heappush(node_list,(dis+1,nx,ny))
if cnt<M+1:
    print(-1)
else:
    print(result)

 이 문제는 MST와 너비 우선 탐색을 활용한 문제였다.

일단 경계선은 전부 1로 되어있으므로, 경계체크를 해줄 필요는 없다.

문제를 푸는 아이디어는 다음과 같다. 

프림알고리즘을 이용한다.

그런데 프림 알고리즘을 활용할려면, 각 노드 사이의 간선의 정보를 알아야한다.

이 것은 BFS를 통해 로봇과 K들 사이의 간선들을 구하는 것이다.

즉, heap에 들어온 Node를 기준으로 다른 열쇠들 간의 간선의 정보를 찾으면 된다.

그래서 프림 알고리즘을 해서 나오는 노드를 기준으로 BFS를 돌리고, 열쇠이고, 현재 누적된 거리가 더 짧으면

거리를 갱신하고, 그 때의 위치 정보 및 거리를 heap에 넣어준다.

이런식으로 해서 프림알고리즘을 돌리면서 매번 BFS를 돌려서 해당 노드에서 다음노드로 갈수 있는 간선정보를 찾아

heap에 넣어주는 식으로 해주면 된다.

그리고 여기서 주의해야할 점은 모든 열쇠를 찾지 못하는 경우도 있다.

우리는 총 M + 1개의 노드를 가진 그래프에서 프림 알고리즘을 돌린것과 마찬가지이므로,

프림 알고리즘에서 방문한 노드의 수가 M+1개 보다 적으면 -1을 출력 해주며 된다.

import sys
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]
 
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
 
    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
 
def input():
    return sys.stdin.readline().rstrip()
 
N,M = map(int,input().split())
 
 
dire = {
    "U": [-1,0],
    "L": [0,-1],
    "R" : [0, 1],
    'D': [1,0]
}
 
arr = [list(input()) for _ in range(N)]
make_set = [i for i in range(N*M)]
ranks = [1 for _ in range(N*M)]
 
 
for x in range(N):
    for y in range(M):
        point = x*M+y
        dx,dy = dire[arr[x][y]]
        next_point = (x+dx)*M+y+dy
        union(point,next_point)
 
result = 0
for x in range(N):
    for y in range(M):
        point = x*M+y
        if point == find_parents(point):
            result += 1
print(result)

 이 문제는 union find를 통해 집합이 몇개가 되는지 확인하면 된다.

그 방법은 현재 노드와 부모노드가 동일한 개수를 세주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
N,M = map(int,input().split())
 
 
dire = {
    "U": [-1,0],
    "L": [0,-1],
    "R" : [0, 1],
    'D': [1,0]
}
arr = [list(input()) for _ in range(N)]
visited = [[-1 for _ in range(M)] for _ in range(N)]
 
result = 0
for x in range(N):
    for y in range(M):
        if visited[x][y] != -1:
            continue
 
        point = x*M+y
        nx,ny = x,y
        while visited[nx][ny] == -1:
            visited[nx][ny] = point
            dx,dy = dire[arr[nx][ny]]
            nx = nx + dx
            ny = ny + dy
        if visited[nx][ny] == point:
            result += 1
print(result)

다르게 푸는 방식은 visited를 만들어놓고 같은 point가 되는 지점에 돌아왔을때 result + 1 해주는 것이다.

안전지대가 된다는 것은 한 지점에서 출발했다가 원래지점으로 돌아온다는것을 뜻하므로, 그 조건을 만족하는 개수를 세주면 된다.