Coding 공부

M,N = map(int,input().split())
def string_fun(num):
    temp = []
    for st in num:
        temp.append(num_st[int(st)])
    return ''.join(temp)
arr = []
for num in range(M,N+1):
    arr.append(str(num))

num_st = ['zero','one','two','three','four','five','six','seven','eight','nine']
arr.sort(key=string_fun)


for i in range(len(arr)//10):
    print(*arr[i*10:(i+1)*10])

if len(arr)%10:
    for i in range(len(arr)-len(arr)%10,len(arr)):
        print(arr[i],end=' ')

sort에 key를 줘서 정렬을 했다.

import sys
import math
def input():
    return sys.stdin.readline().rstrip()
def check(mid):
    cnt = 0
    for time in arr:
        temp = math.ceil(mid/time)
        cnt += temp
    return cnt

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

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


left = 0
right = (N//M+1)*30+1

result = 0
while left+1<right:
    mid = (left+right)//2
    if check(mid)>=N:
        right = mid
    else:
        left = mid

result = 0
prev_person = check(right-1)
remain_cnt = N - prev_person
for i in range(M):
    temp = math.ceil(right/arr[i]) - math.ceil((right-1)/arr[i])
    if temp>0:
        remain_cnt -= temp
        if not remain_cnt:
            result = i
print(result+1)

 이분탐색을 활용한 문제이다. 이 문제를 푸는 방법은 다음과 같다.

모든 인원이 탈수 잇는 시간을 구하고, 그 시간을 가지고 마지막 탑승할 놀이기구를 찾는것이다. 

먼저 모든인원이 탈수 있는 시간을 이분탐색으로 먼저 찾는 것이다.

이분탐색으로 특정시간을 구하고, 그 특정시간에 놀이기구에 탑승할 수 있는 인원을 구한다.

그리고 인원이 전부 탈수 있는 최소한의 시간을 구하면 되는 것이다.

그러면 우리가 구한 right는 N명의 어린아이들을 모두 태울수 있는 시간인것이다.

그러면 right-1은 N명의 어린아이를 태우지 못하는 직전의 시간이다.

그래서 우리는 전체 N명에서 right-1에서 태울수 있는 어린아이의 수를 구하고,

남은 수를 가지고 마지막 아이가 탈 놀이기구의 번호를 찾을 수 있다.

찾는 방법은 현재 시간에서 직전시간의 인원을 빼서 0이 아니라면 right라는 시간에서 인원이 탑승을 하게 된것이다.

그 점을 이용해서 하나씩 빼가면서 remain_cnt가 0이 되었을때의 값을 구하면 된다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def check(mid):
    if mid<0:return 0
    cnt = 0
    for t in range(1,31):
        cnt += (mid//t*time_list[t])
    return cnt + M
N,M = map(int,input().split())

time_list = [0 for _ in range(31)]
arr = list(map(int,input().split()))
for t in arr:
    time_list[t] += 1
left = -1
right = (N//M+1)*30+1

while left+1<right:
    mid = (left+right)//2

    if check(mid)>=N:
        right = mid
    else:
        left = mid


remain_cnt = N - check(right-1)
for i in range(M):
    if not right%arr[i]:
        remain_cnt -= 1
        if not remain_cnt:
            print(i+1)
            break

위 풀이는 동일한데 math.ceil을 쓰지않는 풀이이다.

최초 0초에 탑승하는걸 별도로 M으로 빼주고 그 이후의 시간대에서 탑승한 것을 세준 것이다.

풀이 방법 자체는 동일하다.

import sys
import heapq
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

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



INF = float('inf')
step_trash = [[INF for _ in range(M)] for _ in range(N)]
arround_trash = [[INF for _ in range(M)] for _ in range(N)]

arround_trash_can = [[0 for _ in range(M)] for _ in range(N)]


arr = []
start = []
flower = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'S':
            start = (x,y)
        elif temp[y] == 'F':
            flower = (x,y)
    
    arr.append(temp)
dx = [-1,1,0,0]
dy = [0,0,-1,1]


for x in range(N):
    for y in range(M):
        if arr[x][y] == 'g':
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] == '.':
                        arround_trash_can[nx][ny] = 1

node_list = []

heapq.heappush(node_list,(0,0,start[0],start[1]))

step_trash[start[0]][start[1]] = 0
arround_trash[start[0]][start[1]] = 0
visited = [[True for _ in range(M)] for _ in range(N)]

while node_list:
    s_t,p_t,x,y = heapq.heappop(node_list)

    if not visited[x][y]:
        continue
    visited[x][y] = False


    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] == 'g':
                if step_trash[nx][ny] > s_t + 1:
                    step_trash[nx][ny] = s_t + 1
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny], arround_trash[nx][ny], nx, ny))
            else:
                if step_trash[nx][ny] > s_t:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))
                elif step_trash[nx][ny] == s_t and arround_trash[nx][ny] > p_t + arround_trash_can[nx][ny]:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] =  p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))






x,y = flower

print(step_trash[x][y] , arround_trash[x][y])

이 문제를 지문을 이해하는데 어려움을 겪었던 문제였다. 

문제를 제대로 읽어야하는데 빈 공간을 갈때 주변의 쓰레기 개수와 상관없이 1개이든 4개이든 1번의 불쾌함으로 측정을 해야한다.

그러므로 이 점을 주의해서 우선순위를 설정을 해서 다익스트라를 해줘야한다.

다익스트라를 돌리기전에 사전 작업을 했는데, 쓰레기인 구역을 찾아서

그 주변에 빈공간이 있으면 arround_trash_can라는 배열에 1로 표시를 해줬다.

그래서 arround_trash_can이라는 배열에 0이 아닌 1이 표시된 부분은 쓰레기가 존재하는 옆칸을 지나가는 것이다.

이 문제에서 형택의 여자친구는 쓰레기를 지나가는 것을 가장 싫어하고, 쓰레기 옆을 지나가는 것을 두번째로 싫어한다고 되어있다.

그러므로 heapq에 우선순위를 쓰레기를 지나가는 것 s_t를 가장 앞에 두었고, 쓰레기 옆을 지나가는 개수인 p_t를 두번째 인자로 넣어주었다.

이렇게 한뒤 형택이 상하좌우로 움직이면서 쓰레기인 칸을 밟았을때에는 step_trash의 값과 비교를 해서 더 낮은 값이면, 갱신을 하고 넣어주었다.

그리고 빈공간일때에는 먼저 쓰레기를 밟는 개수가 더 작은 경우인지 확인을 한 뒤, 더 작으면 값을 갱신하고 heapq에 넣어준다.

근데 그게 아니라 쓰레기를 밟는 개수는 동일하다면, 쓰레기 옆을 지나간 횟수를 비교를 해서 heapq에 넣어준다.

이 문제에서 주의해야했던 점은 쓰레기 옆을 지나가는 유무를 구분하는 것이지, 빈공간 옆의 쓰레기의 개수를 세는

것이 아니였던 점이다.

요즘 무엇인가 바쁜일이 있어서 글이 좀 뜸하게 됬네요. 9월달부터 다시 작성할것 같습니다.

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개씩으로 만들어줘야한다.

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