Coding 공부

def find_favorite_seat(num,fa_list):
    max_list = [[[] for _ in range(5)] for _ in range(5)]
    for x in range(N):
        for y in range(N):
            if arr[x][y] == 0:
                favorite_cnt = 0
                empty_cnt = 0
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<N and 0<=ny<N:
                        if arr[nx][ny] == 0:
                            empty_cnt += 1
                        elif arr[nx][ny] in favorite_students:
                            favorite_cnt += 1
                max_list[favorite_cnt][empty_cnt].append((x,y))

    for fa_c in range(4,-1,-1):
        for em_c in range(4,-1,-1):
            if max_list[fa_c][em_c]:
                max_list[fa_c][em_c].sort()
                arr[max_list[fa_c][em_c][0][0]][max_list[fa_c][em_c][0][1]] = num
                return
                    
            




N = int(input())
# (r행 c열)

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

dx = [-1,1,0,0]
dy = [0,0,-1,1]
student_dict = {}
for _ in range(N**2):
    input_list = list(map(int,input().split()))
    student_number = input_list[0]
    favorite_students = set(input_list[1:])
    student_dict[student_number] = favorite_students
    find_favorite_seat(student_number,favorite_students)

fill_gage = [0,1,10,100,1000]

result = 0
for x in range(N):
    for y in range(N):
        cnt = 0
        num = arr[x][y]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx<N and 0<=ny<N:
                if arr[nx][ny] in student_dict[num]:
                    cnt += 1

        result += fill_gage[cnt]

print(result)

numbers = [0]*500001
N = int(input())
arr = map(int,input().split())
for k in arr:
    numbers[k] += 1
print(max(numbers))

N = int(input())

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

arr.sort()
min_value = 0
if len(arr)%2:
    min_value = arr.pop()
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
else:
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
print(min_value)

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))

from collections import deque
import sys

input = sys.stdin.readline
N, M = map(int,input().split())
recipe_dict = {}
next_node_list = [set() for _ in range(N+1)]
for _ in range(M):
    input_list = list(map(int,input().split()))
    recipe = input_list[1:-1]
    liquid_number = input_list[-1]
    recipe.sort()
    if recipe_dict.get(liquid_number):
        recipe_dict[liquid_number].append([set(recipe),input_list[0]])
    else:
        recipe_dict[liquid_number] = [[set(recipe),input_list[0]]]

    for num in recipe:
        next_node_list[num].add(liquid_number)

L = int(input())
own_liquid = list(map(int,input().split()))
possible_list = [False]*(N+1)
result = set()
for num in own_liquid:
    possible_list[num] = True
    result.add(num)
queue = deque(own_liquid)
while queue:
    cur_num = queue.popleft()

    next_nodes = next_node_list[cur_num]

    for next_node in next_nodes:
        if possible_list[next_node]:
            continue
        for ind in range(len(recipe_dict[next_node])):
            recipe = recipe_dict[next_node][ind][0]
            cnt = recipe_dict[next_node][ind][1]

            if cur_num in recipe:
                cnt -= 1
                recipe.remove(cur_num)
                recipe_dict[next_node][ind][0] = recipe
                recipe_dict[next_node][ind][1] = cnt
                if cnt == 0:
                    possible_list[next_node] = True
                    queue.append(next_node)
                    result.add(next_node)


print(len(result))
result = sorted(list(result))
print(*result)

import sys

input = sys.stdin.readline

N,M = map(int,input().split())
recipe_remain_cnt = []
liquid_number = []
next_recipe_array = [[] for _ in range(N+1)]
for i in range(M):
    k,*recipe,r = map(int,input().split())

    recipe_remain_cnt.append(k)
    liquid_number.append(r)

    for num in recipe:
        next_recipe_array[num].append(i)


L = int(input())
own_liquid = list(map(int,input().split()))
result = set(own_liquid)


while own_liquid:
    cur_num  = own_liquid.pop()
    for recipe_idx in next_recipe_array[cur_num]:
        recipe_remain_cnt[recipe_idx] -= 1
        if recipe_remain_cnt[recipe_idx] == 0 and liquid_number[recipe_idx] not in result:
            own_liquid.append(liquid_number[recipe_idx])
            result.add(liquid_number[recipe_idx])

print(len(result))
result = sorted(list(result))

print(*result)

L,H,W = map(int,input().split())


arr = [list(input()) for _ in range(H)]
answer = []


for i in range(L):
    start_y = i*W
    flag = False
    for y in range(start_y,start_y+W):
        for x in range(H):
            if arr[x][y] != '?':
                answer.append(arr[x][y])
                flag = True
                break
        if flag:
            break
    else:
        answer.append('?')
print(''.join(answer))

N = int(input())

def bubble(arr,tc):
    global score
    all_row = set(range(6))
    remove_arr = set()
    empty_arr = set()
    for row in range(5,-1,-1):
        if sum(arr[row]) == 4:
            remove_arr.add(row)
        elif not sum(arr[row]):
            empty_arr.add(row)

    remain_row = sorted(list(all_row - remove_arr - empty_arr))
    temp = []
    while len(remain_row) > 4:
        remain_row.pop()

    for _ in range(6-len(remain_row)):
        temp.append([0]*4)
    for row in remain_row:
        temp.append(arr[row][:])
    score += len(remove_arr)
    return temp





def move(arr,block_type,x,y,tc):
    global score
    if block_type == 1:
        for row in range(6):
            if arr[row][y]:
                arr[row-1][y] = 1
                break
        else:
            arr[row][y] = 1
    elif block_type == 2:
        for row in range(6):
            if arr[row][y] or arr[row][y+1]:
                arr[row-1][y] = 1
                arr[row-1][y+1] = 1
                break
        else:
            arr[row][y] = 1
            arr[row][y+1] = 1
    else:
        for row in range(5):
            if arr[row][y] or arr[row+1][y]:
                arr[row][y] = 1
                arr[row-1][y] = 1
                break
        else:
            arr[row][y] = 1
            arr[row+1][y] = 1
    return bubble(arr,tc)

blue_arr = [[0]*4 for _ in range(6)]
green_arr = [[0]*4 for _ in range(6)]


score = 0
for tc in range(N):
    # 1번 1칸 2번 가로 2칸 3번 세로 2칸
    block_type,x,y = map(int,input().split())
    green_arr = move(green_arr,block_type,x,y,tc)
    if block_type == 2:
        block_type = 3
    elif block_type == 3:
        block_type = 2
    blue_arr = move(blue_arr,block_type,y,x,tc)

print(score)
total_block = sum(map(sum,green_arr)) + sum(map(sum,blue_arr))
print(total_block)

from collections import deque

def rotate(start,lens,arr):
    x,y = start
    rotated_arr = [[0]*lens for _ in range(lens)]

    for i in range(lens):
        for j in range(lens):
            rotated_arr[j][lens-i-1] = arr[x+i][y+j]

    for i in range(lens):
        for j in range(lens):
            arr[x+i][y+j] = rotated_arr[i][j]

def bfs(x,y):
    global max_block,col_size
    stack = deque()
    stack.append((x,y))
    cnt = 0
    visited[x][y] = False
    while stack:
        x,y = stack.popleft()
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<col_size and 0<=ny<col_size:
                if arr[nx][ny] and visited[nx][ny]:
                    stack.append((nx,ny))
                    visited[nx][ny] = False
    if cnt > max_block:
        max_block = cnt




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


arr = [list(map(int,input().split())) for _ in range(2**N)]
col_size = 2**N
total_size = (col_size)**2

L = list(map(int,input().split()))
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for k in L:
    lengths = 2**k
    size = lengths**2
    start = (0,0)
    cnt = 0
    while cnt < total_size//size:
        rotate(start,lengths,arr)
        start = (start[0],start[1]+lengths)
        if start[1] >= col_size:
            start = (start[0]+lengths,0)
        cnt += 1
    melt_down = []
    for x in range(col_size):
        for y in range(col_size):
            temp = 0
            if arr[x][y]:
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<col_size and 0<=ny<col_size:
                        if arr[nx][ny]:
                            temp += 1
                if temp <3:
                    melt_down.append((x,y))
    if melt_down:
        for x,y in melt_down:
            arr[x][y] -= 1
    
print(sum(map(sum,arr)))
max_block = 0
visited = [[True]*col_size for _ in range(col_size)]
for x in range(col_size):
    for y in range(col_size):
        if arr[x][y] and visited[x][y]:
            bfs(x,y)
print(max_block)