Coding 공부

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

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


def count_group(val):
    k = 0
    temp = 0
    for ind in range(N):
        temp += arr[ind]
        if temp>=val:
            k += 1
            temp = 0
    return k


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

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


left = 0
right = sum(arr)+1

while left+1<right:
    mid = (left+right)//2
    K_mid = count_group(mid)
    if K_mid >= K:
        left = mid
    else:
        right = mid
print(left)

 원래 잘 못푸는 이분탐색 문제라서 오래걸렸던 문제였다.

이 문제에서 구해야할 것은 최소의 최대값이다.

즉 여기서 mid의 값이 의미하는 것은 해당 시험 문제지의 최소 점수인것이다.

즉 이 최소 점수가 넘어가면, 그룹을 나누는것이다.

이렇게 나눈 최소 점수를 기준으로 시험지를 나눴을때의 그룹의 수가  K개 미만이 되면 False K개 이상이 되면 True로 하고

우리는 K개 이상의 가장 마지막 값을 구하고 싶은 것이므로, left를 출력해주면 된다.

이 문제 덕분에 이분탐색에 대해서 감을 잡게 되었고,

찾고 싶은 값이 있을때 어떻게 나눠야할지 대략 감을 잡았다.

아직 부족하지만, 어떻게 나눠야할지 알게 되었다.

https://blog.naver.com/jinhan814/222156334908

https://blog.naver.com/jinhan814/222135038870

https://eine.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89binary-search-%EA%B5%AC%ED%98%84%EC%8B%9C-%EA%B3%A0%EB%A0%A4%ED%95%A0-%EA%B2%83%EB%93%A4

https://blog.naver.com/kks227/220777333252

풀면서 참조한 블로그들이다. 이분탐색에 대해 잘 설명을 해놓은 블로그이니 추천을 드린다.

import sys

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


def check(mid):
    idx = 0
    temp = []
    cnt = 0
    while idx<N:
        if cnt >M:
            return False
        if temp:
            min_value,max_value = min(temp),max(temp)
            if abs(arr[idx]-min_value)>mid or abs(arr[idx]-max_value)>mid:
                cnt += 1
                temp = [arr[idx]]
            else:
                temp.append(arr[idx])
        else:
            temp.append(arr[idx])
        idx += 1
    if temp:
        cnt += 1
    if cnt>M:
        return False
    return True
        

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

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


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

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

print(right)

이 문제는 구간의 최대값과 최소값을 비교한 값이 최대가 되어야하고 M개 이하의 그룹으로 나뉘어야한다.

이 문제를 푸는 법은 이분탐색을 이용해서 풀면된다. 이분탐색의 탐색근거가 되는 값은 최대-최소의 값이다.

이 값이 벗어나는 경우 새로운 그룹을 만들어주고, 총 그룹의 수가 M개 초과가 되면 False를 만족하면 True로 하면서

True를 만족 최소의 값을 구하면 된다.

위의 풀이는 list에 계속 넣다 빼다보니 시간이 좀 오래걸린다.

import sys

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


def check(mid):
    min_value = arr[0]
    max_value = arr[0]
    idx = 1
    cnt = 1
    while idx<N:
        if cnt>M:
            return False
        if min_value>arr[idx]:
            min_value = arr[idx]
        if max_value < arr[idx]:
            max_value = arr[idx]
        
        if max_value-min_value>mid:
            min_value = arr[idx]
            max_value = arr[idx]
            cnt += 1
        idx += 1
    if cnt>M:
        return False
    else:
        return True
        

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

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


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

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

print(right)

똑같은 원리지만, 훨씬 빠른 풀이다. 리스트를 저장하는게 아니라, 최소 최대값을 계속 갱신을 해주면서,

그 값이 주어진 mid보다 크면, 최소 최대값을 현재 탐색중인 값으로 초기화 해준뒤 cnt를 늘려주면 된다.

이 풀이가 좀 더 깔끔한 풀이라 생각한다.

import sys
input = sys.stdin.readline
INF = (10**12)+1

def get_process(mid_priority):
    global N
    if dp.get(mid_priority):
        return dp[mid_priority]
    else:
        total_process_cnt = 0


        for i in range(N):
            process = arr[i]

            if mid_priority<=process.sp:
                total_process_cnt += process.time
            elif process.sp< mid_priority<=process.ep:
                total_process_cnt = total_process_cnt + process.ep - mid_priority +1
        
        dp[mid_priority] = total_process_cnt
        return total_process_cnt


def b_search(target_T):
    left = 0
    right = INF*2
    while left<=right:
        mid = (left+right)//2
        total_cnt = get_process(mid)
        if total_cnt>=target_T:
            next_priority_cnt = get_process(mid+1)
            if next_priority_cnt<target_T:
                remain_priority_cnt = target_T - next_priority_cnt
                for i in range(N):
                    if arr[i].sp <= mid <=arr[i].ep:
                        remain_priority_cnt -= 1
                        if remain_priority_cnt == 0:
                            result.append(arr[i].process_id)
                            break
                break
            else:
                left = mid + 1

        else:
            right = mid-1


class Process:
    def __init__(self,_id,_spend_time,_init_priority):
        self.process_id = _id
        self.time = _spend_time
        self.ep = _init_priority+INF
        self.sp = _init_priority+INF-spend_time+1


Q,N = map(int,input().split())
arr = []
for _ in range(N):
    process_id,spend_time,init_priority = map(int,input().split())
    new_process = Process(process_id,spend_time,init_priority)
    arr.append(new_process)
dp = {}
arr.sort(key=lambda x : x.process_id)
result = []

for _ in range(Q):
    find_time = int(input())

    b_search(find_time)


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

이 문제 또한 앞선 문제와 같이 혼자서 풀기 어려운 난이도라, https://github.com/cdog-gh/gh_coding_test 해설을 보고 푼 문제이다.

이 문제는 boj.kr/21773 과 boj.kr/21777 문제를 이해해야지만 풀 수 있는 문제였다.

앞서 21777에서 말한것처럼  초기 priority가 P라 하고, 총 실행시간이 T라한다면,

P~ (P-T+1) 까지 우선순위를 실행하게 될 것이다.

그러므로 우리는 무지하게 큰 초기값을 각각의 priorty에 더해준다. 왜냐하면, 양수의 priority로만 구분을 해주기 위함이다.

그러므로 INF + P 를 end_priority 그리고 INF + P - T + 1 를 start_priority 로 해주었다.

근데 숫자가 커서 end_priority와 start_priority라 했지만, 이 문제를 더 쉽게 이해하기 위해선 반대로 바꾸는것도 한다.

왜냐하면 우선순위가 클수록 먼저 실행이 되기 때문이다.

그러면 우리는 시간 T를 찾는것이다.

시간 T를 찾는 방법은 다음 과 같다. 특정 priority일때까지 실행된 모든 프로세스의 개수를 세주는 것이다.

priority가 실행된 개수가 곧 실행시간이기 때문이다.

여기서 주의해야할점은 get_process(priority) == T 를 만족하는 priority가 많을 것이다.

그러므로, 우리는 priority가 현재보다 1이 커졌을때 T보다 작아지는 경우를 찾아야,

구하고자하는 실행시간 T에 실행되는 process를 찾을 수 있다.

나머지는 이분탐색처럼 하면 되는데 여기서 주의해야할점은 다음과 같다.

priority가 높을수록 일찍 실행되고, 낮을수록 늦게 실행된다.

만약 K라는 priorty까지 실행되는 priority의 개수를 구해야한다면,

K <= start_priority 와 같다면, 이 process_id가 가진 모든 실행시간을 쓴 것이기 때문에 전부 더해주면 된다.

그리고 start_priority < K <= end_priority 일때에는

end_priority - K + 1까지가 프로세스가 실행된 것이기 때문에 이 부분을 더해주면 된다.

마지막으로, 우리가 구한 get_process(mid_priority) >= T  와 get_process(mid_priority+1)<T를

만족하는 mid_priority에서 실제로 실행된 priority를 구해야한다.

get_process(mid_priority)  - get_process(mid_priority+1) 을 빼준값을 remain_priority_cnt라 하고

id 1부터 해서 mid_priorty가 해당 프로세스의 start_point와 end_point 사이에 있으면  이 값을 한개씩 줄여주면서 

0이 되었을때 실제로 실행된 process_id이므로 그때의 process_id를 출력해주면 된다.

그리고, get_process에서 특정 process에 대한 total_cnt는 동일할것이기 때문에 캐싱을 해주면 된다.

또한 dp테이블로 만든게 아닌, 함수이므로, functools의 lru_cahce를 이용하는 방법도 있다.

N,M = map(int,input().split())
arr =  [ int(input()) for _ in range(N)]
left = max(arr)
right = 100000001
answer = float('inf')
while left<=right:
    mid = (left+right)//2
    temp = mid
    cnt = 1
    for num in arr:
        if temp >= num:
            temp -= num
        else:
            temp = mid - num
            cnt += 1
    
    if cnt >M:
        left = mid + 1
    else:
        right = mid - 1
        answer = min(answer,mid)

print(answer)

N = int(input())
K = int(input())
ST,EN = 1,K
while ST<=EN:
    mid = (ST+EN)//2
    cnt = 0
    for i in range(1,N+1):
        cnt += min(mid//i,N)

    if cnt < K:
        ST = mid + 1
    else:
        EN = mid -1

print(ST)

코드는 간단하지만, 어려웠던 문제였다.

자세한 설명은 다른 사람 블로그를 참조하길 바란다.

몇몇 케이스를 해보면 알지만 K번째의 수는 절대 K를 넘을 수가 없다.

이점을 이용해 1,K로 이분탐색을 한다.

각 행을 i라고 하면, 각 행은 i의 배수이다. 

즉 N = 5라고 하면 총 5행이 있고, 우리가 찾고자 하는 T = 12 라고 하면

1행에서 12보다 작거나 같은 값은 1,2,3,4,5          T//1 = 12

2행에서 12보다 작거나 같은 값은 2,4,6,8,10        T//2 = 6

3행에서 12보다 작거나 같은 값은 3,6,9,12,          T//3 = 4

4행에서 12보다 작거나 같은 값은 4,8,12,            T//4 = 3

5행에서 12보다 작거나 같은 값은 5,10               T//5 = 2

위와 같이 보면 우리가 찾고자 하는 값보다 작은 값의 개수는 각 행의 값을 나눈 몫 만큼이다. 그리고 각 행의 열의 개수는 N이므로, N과 비교해서 최소값으로 한다.

이분 탐색을 반복하면서 특정 값보다 작거나 같은 값의 개수가 K개가 될때까지 반복해준다. 또한 ST == END가 될때까지 반복해준다. 왜냐하면 K가 되는 값이 여러개가 될수 있으므로, 특정해줘야한다.

K개 에서 그냥 빠져 나올 경우 

N=52, K=276

에서 답이 잘못 나온다.