번개맨 쉼터

시간초과

def solution():
    # 첫 번째 장애물은 항상 석순
    # 종유석과 석순이 번갈아가면서 등장 
    # N 만큼 경로 선택 가능

    # 석순의 경우 : (H -1) 만큼 방해
    # 종유석의 경우 : (H-1) 만큼 방해
    # 종유석과 석순이 번갈아 나오는 것을 특징으로 (Graph 그려서 풀기에 많음)


    pass

if __name__ == '__main__':
    N,H = map(int,input().split()) # N은 항상 짝수 (N길이 미터, H 높이 미터)
    
    gate = []
    for _ in range(N):
        gate.append(int(input()))

    # 1구간 : +=1 개수
    # 2구간 : +=1 개수
    # 3구간 : +=1 개수
    # (0,1) (1,H-3) (2,4)
    routes = [0 for _ in range(H)] # 라인 충돌 개수

    for x in range(N):
        석순 = True; 종유석 = False
        if x % 2 == 0:
            석순 = True; 종유석 = False
        if x % 2 == 1:
            석순 = False; 종유석 = True

        if 석순 == True:
            for i in range(gate[x]):
                routes[i] +=1
        if 종유석 == True:
            for i in range(-1,-gate[x]-1,-1):
                routes[i] +=1
    
    count = 0        
    routes.sort() # 정렬
    for route in routes:
        if routes[0] != route:
            break
        count +=1

    print(routes[0],count)

성공코드

# 모범답안
import sys
input = sys.stdin.readline

n, h = map(int, input().split(" "))

# 누적합 이용
lines = [0] * h

for i in range(n):
    high = int(input())
    # 석순
    if i % 2 == 0:
        lines[h - high] += 1
    # 종유석
    else:
        lines[0] += 1
        lines[high] -= 1
        
# 누적합
for i in range(1, h):
    lines[i] += lines[i - 1]
    
# 최소값 체크 및 최소값 갯수 체크
count = 0
low = min(lines)
for i in lines:
    if i == low:
        count += 1
        
print(low, count)

import sys
sys.setrecursionlimit(100000)
def dfs(target,numbers,visited,idx,cnt):
    answer = 0

    if not(False in visited): # 전부 방문하였을때,
        if cnt == target:
            return 1
        return 0
    if visited[idx] == False:
        visited[idx] = True
        answer += dfs(target,numbers,visited,idx+1,cnt + (numbers[idx] * -1))
        answer += dfs(target,numbers,visited,idx+1,cnt+ (numbers[idx]))
        visited[idx] = False

    return answer


def solution(numbers, target):

    visited = [False for _ in range(len(numbers))]
    answer = dfs(target,numbers,visited,idx=0,cnt=0)
    return answer

import math
def 비교(min_row,min_col,row,col):
    """
    입력값으로 들어온 가로,세로 길이 크기 비교를 통해
    가로 세로 길이 추출, 넓이 return
    """
    temp_col = min_col; temp_row = min_row
    if min_col < col:
        temp_col = col
    if min_row < row:
        temp_row = row

    temp_rect = temp_col * temp_row

    return temp_rect,temp_col,temp_row

def solution(sizes):
    answer = 0

    min_col = 0; min_row = 0; min_rect = math.inf
    for size in sizes:

        # 회전 X
        row,col = size[0],size[1]
        넓이1,가로1,세로1 = 비교(min_col,min_row,row,col)

        # 회전 O
        row,col = size[1],size[0]
        비교(min_col,min_row,row,col)
        넓이2,가로2,세로2 = 비교(min_col,min_row,row,col)

        # 가로,세로 길이 업데이트
        # 작은 넓이를 만들어내는 지갑의 가로,세로 길이, 넓이 저장
        min_rect=min(넓이1,넓이2)
        if min_rect == 넓이1:
            min_row,min_col =가로1,세로1
        if min_rect == 넓이2:
            min_row,min_col =가로2,세로2

    answer = min_rect
    return answer

if __name__ == "__main__":
    sizes = [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]
    print(solution(sizes))
    pass

def solution(n, times):
    times.sort() # 정렬
    start = 1; end = times[-1] * n # 최대 시간
    while start <= end:
        mid = (start + end) // 2
        people = 0
        for refree in times:
            people += mid// refree
            if people > n:
                break        
        if people >= n:
            end = mid - 1
            answer = mid
        else:
            start = mid + 1
    
    return answer



if __name__ == "__main__":
    n = 6; times=[7,10]
    solution(n,times)