Coding 공부

import sys

input = sys.stdin.readline


while True:
    N,*arr = list(map(int,input().split()))

    if N == 0:
        break

    stack = [0]
    arr = [0] + arr[:] +[0]
    result = 0
    for ind in range(1,len(arr)):
        while stack and arr[ind] < arr[stack[-1]]:
            height = arr[stack[-1]]
            stack.pop()
            width = ind - stack[-1]-1
            result = max(result,height*width)
        stack.append(ind)

    print(result)

 이 문제는 boj.kr/11873 의 하위호환이다.

11873의 문제를 푼것과 같이 stack에 현재위 index 즉 가로길이를 넣어주는 걸 한다.

그리고 이걸 좀 더 쉽게 구하기 위해, 양 끝에 [0]을 추가를 해준다.

그러면 스택에서 마지막 값에 위치한 높이보다 작은 높이가 들어오면,

그때 스택에서 값을 추출해서, 지금까지의 거리를 측정을 해준다.

측정 방식은 현재 index에서 stack의 마지막값을 빼준 값에 -1을 해준것이다.

이렇게 2개의 값을 곱한뒤 최대값을 저장해주면 된다. 

def find_K(k,n,reversal):
    if n == 0:
        return reversal%2
    else:
        if k >= 2**(n-1):
            return find_K(abs(2**(n-1)-k),n-1,reversal+1)
        else:
            return find_K(k,n-1,reversal)

k = int(input())
k = k-1
print(find_K(k,60,0))

def check(x,y,size):
    for nx in range(x,x+size):
        for ny in range(y,y+size):
            if result[nx][ny] != 0:
                return False
    return True


def divide_and_fill(x,y,size):
    global numbers
    numbers += 1
    next_size = size//2
    input_position = [[x+next_size-1,y+next_size-1],[x+next_size,y+next_size-1],[x+next_size-1,y+next_size],[x+next_size,y+next_size]]
    for ind,val in enumerate([[x,y],[x+next_size,y],[x,y+next_size],[x+next_size,y+next_size]]):
        sx,sy = val
        input_x,input_y = input_position[ind]
        if check(sx,sy,next_size):
            result[input_x][input_y] = numbers

    if size == 2:
        return
    divide_and_fill(x,y,next_size)
    divide_and_fill(x+next_size,y,next_size)
    divide_and_fill(x,y+next_size,next_size)
    divide_and_fill(x+next_size,y+next_size,next_size)




k= int(input())
N = 2**k
input_x,input_y = map(int,input().split())
x = N-input_y
y = input_x-1
result = [[0 for _ in range(N)] for _ in range(N)]
result[x][y] = -1

numbers = 0
divide_and_fill(0,0,N)
for row in result:
    print(*row)