Coding 공부

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

T = int(input())

N = int(input())
A_arr = [0] + list(map(int,input().split()))

M = int(input())
B_arr = [0] +list(map(int,input().split()))


for i in range(N):
    A_arr[i+1] += A_arr[i]

for j in range(M):
    B_arr[j+1] += B_arr[j]

A_nums = defaultdict(int)
B_nums = defaultdict(int)
for i in range(1,N+1):
    for j in range(i):
        A_nums[A_arr[i] - A_arr[j]] += 1

for i in range(1,M+1):
    for j in range(i):
        B_nums[B_arr[i] - B_arr[j]] += 1

result = 0
for num in A_nums:
    find_num = T -num
    if B_nums.get(find_num):
        result = result + A_nums[num] * B_nums[find_num]

print(result)

이 문제는 누적합을 이용해 풀었다. 이 문제는 다음과 같다. 두 배열이 주어지고,

두 배열의 원소들을 더해서 T가 나올 수 있는 경우의 수를 구하는 문제이다.

그래서 먼저 사전 작업을 해주었다.

각 배열들을 전부 누적합을 통해 특정 구간의 전체 합을 구하기 쉽게 만들어줬다.

이렇게 누적합을 미리 준비해주고,

j ->i 까지의 나올수 있는 모든 종류의 부분 합을 dict 에 저장을 해준다.

이렇게 사전 준비 작업을 했으면,

A_nums 라는 A 배열에서 나올 수 있는 모든 부분 배열의 합의 종류들의 key 값으로 탐색을 해준다.

T 에서 A에서 나올 수 있는 배열의 합을 뺀 값이 B에 존재 하면,

이 두 배열의 값들로 만들 수 있는 경우의 수는 A_nums[num] * B_nums[find_num]이 된다.

이 값들을 구해서 결과 값을 출력해주면 된다.

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

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

sys.setrecursionlimit(20000)

def solution(k, num, links):
    left = sum(num)//k
    right = sum(num)
    N = len(num)
    degrees = [0 for _ in range(N)]
    for ind in range(N):
        if links[ind][0] != -1:
            degrees[links[ind][0]] += 1
        if links[ind][1] != -1:
            degrees[links[ind][1]] += 1
    root = -1
    for ind in range(N):
        if not degrees[ind]:
            root = ind
            break
    INF = float('inf')
    def check(node):
        nonlocal links,INF,dp,mid
        if links[node][0] == -1 and links[node][1] == -1:
            if num[node]<=mid:
                dp[node][0] = num[node]
                dp[node][1] = 1
            else:
                dp[node][0] = 0
                dp[node][1] = INF
        else:
            for ind in range(2):
                if links[node][ind] != -1:
                    check(links[node][ind])
            left_node = links[node][0]
            right_node = links[node][1] 
            if dp[left_node][0] + dp[right_node][0] + num[node] <= mid:
                dp[node][0] = dp[left_node][0] + dp[right_node][0] + num[node]
                dp[node][1] = dp[left_node][1] + dp[right_node][1] -1
                return
            if right_node == -1:
                if num[node] <= mid:
                    dp[node][0] = num[node]
                    dp[node][1] = dp[left_node][1] + 1
                else:
                    dp[node][0] = 0
                    dp[node][1] = INF

            else:
                if num[node] + min(dp[right_node][0],dp[left_node][0])<= mid:
                    dp[node][0] = num[node] + min(dp[right_node][0],dp[left_node][0])
                    dp[node][1] = dp[right_node][1] + dp[left_node][1]
                elif num[node] <= mid:
                    dp[node][0] = num[node]
                    dp[node][1] = dp[left_node][1] + dp[right_node][1] + 1
                else:
                    dp[node][0] = 0
                    dp[node][1] = INF

            



    while left+1<right:
        mid = (left+right)//2
        dp = [[0,1] for _ in range(N+1)]
        check(root)
        if dp[root][1]<=k:
            right = mid
        else:
            left = mid
    return right

풀기 힘들었던 문제이다.

이 문제는 트리 DP와 파라메트릭 서치를 활용한 문제로

k개의 그룹으로 나눌 수 있는 최소 값을 찾는것이다.

카카오 해설에서도 알수 있듯이 이분탐색으로 찾으면 되고,

이 이분 탐색의 중간값인 mid가 의미하는 것은 이 트리를 나눌 최대의 인원을 의미한다.

한 그룹의 인원이 mid가 넘어가지 않게 해주면 된다.

즉 mid의 값이 크면 k는 적게 나올것이고, mid의 값이 작으면 k보다 많게 나올 것이다.

우리는 left+1<right일때 끝나고

left일때 false이므로,

우리가 구하고자 하는 값은 right임을 알 수 있다.

문제에 들어가면,

가장 밑 노드에서부터 해주면 된다.

먼저 dp 테이블은 N*2의 크기로 해주었고,

dp[x][0] 은 x 노드에서의 최소 그룹인원의 수

dp[x][1] 은 x 노드에서의 그룹의 개수를 의미한다.

각 노드는 처음에 하나의 그룹이므로, dp[x][0]은 0으로 dp[x][1]은 1로 초기화를 해주었다.

총 4가지 경우가 있을것이다.

1. 자식노드 2개에 누적된 그룹인원과 현재노드의 인원과  더해도 mid보다 작거나 같다.

    그러면 dp[parent][0] = num[parent] + dp[left_node][0] + dp[right_node][1]이 될것이다.

    그리고 그룹의 수는 자식노드의 그룹의 수를 더해준 것에서 -1을 해준다.

    이러는 이유는 우리가 각 노드를 하나의 그룹으로 생각했기 때문에, 처음에 1로 전부 초기화 되어 있어서 그런다.

   자식노드와 현재그룹을 더해서 한개의 그룹이 된 것이므로 - 1을 해준다.

2. 자식노드 둘 중 1개 그룹인원과  현재 노드의 인원과 더하면 mid보다 작거나 같다.

   이럴때에는 그룹인원이 많은쪽의 간선을 끊는것과 마찬가지 이므로

   dp[parent][0] = num[parent] + min(dp[left_node][0], dp[right_node][1])

  을 해주고, 그룹은 두 자식노드의 그룹인원을 더해주면 된다.

3. 현재 그룹인원의 mid보다 작거나 같고, 자식노드들의 인원을 더하면 mid보다 크다.

   이럴 경우는 간선을 전부 끝는 것이다.

   그래서 dp[parent][0] = num[parent]를 해주고,

   그룹의 수는 1개를 더 더해주면 된다.

4. 현재 그룹의 인원의 mid보다 크다.

   이럴때에는 어떤 방도로도 mid보다 작거나 같은 그룹으로 나눌수 없으므로, 그룹인원의 수를 0으로 초기화 해주고, 그룹의 수를 INF로 해준다.

이 문제는 평소 코에서 나오지 않는 트리dp 문제인데다가, 이분탐색까지 활용해야되서 어려웠던 문제였다.

dp 테이블을 설계하는 것부터, 그룹의수가 k이면서 최소의 그룹인원 수를 어떻게 찾아하는지 생각하기 어려운 문제였다.

이 문제는 카카오 시험이 끝난뒤, 알고리즘 고수분들을 이야기를 통해, 어떻게 풀어야할지 감을 잡았고,

문제가 나오고 실제로 푸는데에도 시간이 오래걸린 문제였다.

이 문제가 다시 나오면 풀수 있다는 확신은 없지만, 한번 경험해봤으니 이러한 문제도 있다라는 것을 배운점에 만족했다.

import sys
import bisect
def time_str_num(times):
    return times[:4]+times[5:7]+times[8:10]+times[11:13]+times[14:16]+times[17:19]

input = sys.stdin.readline

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

lev_list = [[] for _ in range(7)]
for _ in range(N):
    times,lev = input().split('#')
    times = time_str_num(times)
    lev_list[int(lev)].append(times)

result = []

for _ in range(Q):
    s_time,e_time,lev = input().split('#')

    s_time = time_str_num(s_time)
    e_time = time_str_num(e_time)
    lev = int(lev)
    cnt = 0
    for cu_lev in range(lev,7):
        s_ind = bisect.bisect_left(lev_list[cu_lev],s_time)
        e_ind = bisect.bisect_right(lev_list[cu_lev],e_time)
        cnt += (e_ind-s_ind)

    result.append(cnt)


for i in range(Q):
    sys.stdout.write(str(result[i])+'\n')

대회때 시간초과가 났던 문제다.

이 문제는 https://programmers.co.kr/learn/courses/30/lessons/17676 와 https://programmers.co.kr/learn/courses/30/lessons/72414 에서 비슷한 느낌을 받았던 문제이다.

이 2문제 전부 긴 시간대를 주고 문제에 주어진 것에서 최대값을 찾던가, 시간내에 있는 기록등을 찾는 방식이다.

이 문제 또한, 각종 로그들이 특정시간대에 나고, 시작시간과 종료시간 내에 발생한 로그의 개수를 세는 것이다.

푸는 방식은 다음과 같다. 레벨별로 시간을 나눠서 저장을 하는것이다.

어차피 들어오는 로그는 순서대로 들어오기 때문에, 작은순서대로 정렬되어서 들어가진다.

또한 년월일시분초를 다 합쳐서 14글자의 숫자로 저장해주면, 문자열로 저장해놔도, 대소구분이 되기 때문에 괜찮다.

그러면 문제에 주어진 로그들을 맞는 레벨에 하나씩 추가를 해준다.

그리고 로그가 들어오면 시작시간과 끝시간을 분리를 해놓는다.

그리고 이분탐색을 통해, 시작시간은 이 시간이 들어가야할 최소 위치,

끝시간은 이 시간이 들어갈수 있는 최대 위치를 구해준다.

위와 같은 리스트가 있다고 하고,

시작시간은 3이고, 끝시간은 4라 한다면,

시작시간은 2번인덱스을 가리켜야하고, 끝시간은 8번 인덱스를 가리켜야한다.

그러면, 8-2 = 6개가 나오는 걸 볼 수 있다.

이걸 나는 python에서 이분탐색을 위한 라이브러리인 bisect를 이용해서 bisect_left와 bisect_right를 통해 구현을 했다.

그리고 주어진 로그의 레벨이상을 전부 구하는 것이므로, 주어진 레벨에서부터 최대레벨인 6까지 전체 탐색을 해주었다.

import sys
import bisect
def time_str_num(times):
    return times[:4]+times[5:7]+times[8:10]+times[11:13]+times[14:16]+times[17:19]

input = sys.stdin.readline

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

lev_list = [[] for _ in range(7)]
for _ in range(N):
    times,lev = input().split('#')
    times = time_str_num(times)

    for i in range(1,int(lev)+1):
        lev_list[i].append(times)

for _ in range(Q):
    s_time,e_time,lev = input().split('#')

    s_time = time_str_num(s_time)
    e_time = time_str_num(e_time)
    lev = int(lev)
    cnt = 0
    s_ind = bisect.bisect_left(lev_list[lev],s_time)
    e_ind = bisect.bisect_right(lev_list[lev],e_time)
    cnt += (e_ind-s_ind)

    sys.stdout.write(str(cnt)+'\n')

   이 풀이는 위의 풀이와 똑같지만, 반복작업을 없애준 것이다.

 처음 로그가 들어올때부터, 1레벨부터 현재 레벨까지 전부 넣어주는것이다.

어차피 레벨 이상의 쿼리를 전부 조회하는 것이므로, 로그로 들어온 레벨 이하에 전부 저장을 해주고,

이분 탐색을 한번만 해서 출력할 수 있도록 해준 것이다.

대회시간에는 못 풀었지만 류호석님의 조언을 듣고 바로 풀 수 있었던 문제였다.

이전에 풀었던 문제들을 조금만 응용하면 풀수 있는 문제였지만, 제대로 응용하지 못한 패착인것 같다.

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

arr = list(map(int,input().split()))
dp = [0]*(N+1)
result = 0


left = 0
right = 0
sum_temp = 0
while right <=N:
    if sum_temp >=K:
        while sum_temp >= K:
            dp[right] = max(dp[right],dp[left]+sum_temp-K)
            sum_temp -= arr[left]
            left += 1
    else:
        dp[right] = max(dp[right],dp[right-1])
        if right == N:
            break
        sum_temp += arr[right]
        right += 1
print(dp[N])

import sys

sys.setrecursionlimit(100001)
def find_min_right_over_k(left):
    global K
    low = left -1
    high = N
    while low + 1 < high:
        mid = (low+high)//2
        if prefix_sum[mid] - prefix_sum[left-1] >=K:
            high = mid
        else:
            low = mid
    return high




def solution(left):
    if left > N:
        return 0
    if dp[left] != -1:
        return dp[left]
    pass_hear_value = solution(left+1)
    right = find_min_right_over_k(left)
    eat_left_right = prefix_sum[right]-prefix_sum[left-1]-K+solution(right+1)
    max_value = max(pass_hear_value,eat_left_right)
    dp[left] = max_value
    return dp[left]

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

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

dp = [-1]*(N+1)

prefix_sum = [0]+arr[:]
for k in range(1,N+1):
    prefix_sum[k] += prefix_sum[k-1]


print(solution(1))

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

LIS = [arr[0]]
for i in range(1,len(arr)):
    if arr[i] > LIS[-1]:
        LIS.append(arr[i])
    else:
        start = 0
        end = len(LIS)
        idx = len(LIS)-1
        while start < end:
            mid = (start+end)//2
            if LIS[mid] >= arr[i]:
                idx = min(idx,mid)
                end = mid
            else:
                start = mid + 1
        LIS[idx] = arr[i]

LIS_CNT = len(LIS)
print(LIS_CNT)

import sys

input = sys.stdin.readline

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

arr = [0]+[int(input()) for _ in range(N)]

arr.sort()
arr.append(D)
left = 0
right = D
ans = float('inf')
while left<=right:
    mid = (left+right)//2
    cnt = 0
    post_ind = 0
    for ind in range(1,N+2):
        if arr[ind] - arr[post_ind] <= mid:
            cnt += 1
        else:
            post_ind = ind
    
    if cnt > M:
        right = mid -1
    else:
        left = mid + 1

print(left)

import sys
input = sys.stdin.readline

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


arr = [D] + [int(input()) for _ in range(N)]

arr.sort()
left = 0
right = D
ans = 0
while left<=right:
    mid = (left+right)//2
    past_island = 0
    cnt = 0
    for island in arr:
        if island - past_island >= mid:
            cnt += 1
            past_island = island
    
    if cnt >= N-M+1:
        ans = max(ans,mid)
        left = mid + 1
    else:
        right = mid -1

print(ans)