Coding 공부

def dfs(x,y,cnt):
    global result
    if cnt > result:
        return
    if x >= 10:
        result = min(result,cnt)
        return
    if y >= 10:
        dfs(x+1,0,cnt)
        return
    if arr[x][y] == 1:
        for paper_size in range(5,0,-1):
            if paper[paper_size]:
                if x + paper_size <= 10 and y + paper_size <= 10:
                    flag = False
                    for dx in range(paper_size):
                        for dy in range(paper_size):
                            if not arr[x+dx][y+dy]:
                                flag = True
                                break
                        if flag:
                            break
                    if not flag:
                        for dx in range(paper_size):
                            for dy in range(paper_size):
                                arr[x+dx][y+dy] = 0
                        paper[paper_size] -= 1
                        dfs(x,y+paper_size-1,cnt+1)
                        paper[paper_size] += 1
                        for dx in range(paper_size):
                            for dy in range(paper_size):
                                arr[x+dx][y+dy] = 1
    else:
        dfs(x,y+1,cnt)

        


arr = [list(map(int,input().split())) for _ in range(10)]
paper = [0]+[5]*5
result = float('inf')
dfs(0,0,0)
print(result if result != float('inf') else -1)

def check(x,y,size):
    if x + size > 10 or y + size >10:
        return False
    for dx in range(size):
        for dy in range(size):
            if not arr[x+dx][y+dy]:
                return False
    return True


def set_position(x,y,size,val):
    for dx in range(size):
        for dy in range(size):
            arr[x+dx][y+dy] = val
def dfs(x,y,cnt):
    global result
    if cnt >= result:
        return
    finish = True
    while x < 10:
        while y < 10:
            if arr[x][y] == 1:
                finish = False
                for paper_size in range(5,0,-1):
                    if paper[paper_size] and check(x,y,paper_size):
                        set_position(x,y,paper_size,0)
                        paper[paper_size] -= 1
                        dfs(x,y+paper_size-1,cnt+1)
                        paper[paper_size] += 1
                        set_position(x,y,paper_size,1)
                return
            y += 1
        x += 1
        y = 0
    if finish:
        result = min(result,cnt)
        


arr = [list(map(int,input().split())) for _ in range(10)]
paper = [0]+[5]*5
result = float('inf')
dfs(0,0,0)
print(result if result != float('inf') else -1)

import sys



input =sys.stdin.readline

def wall_move(origin_list):
    temp = []

    for x,y in origin_list:
        if x == 7:
            continue
        else:
            arr[x][y] = '.'
            temp.append((x+1,y))
    for x,y in temp:
        arr[x][y] = '#'
    return temp



arr = []
wall = []
for x in range(8):
    input_list = list(input().strip())
    for y in range(8):
        if input_list[y] == '#':
            wall.append((x,y))
    arr.append(input_list)

start = (7,0)

stack = []
stack.append(start)
result = 0
times = 0
dx = [-1,0,1,-1,0,1,-1,0,1]
dy = [-1,-1,-1,0,0,0,1,1,1]
while stack:
    visited = [[True]* 8 for _ in range(8)]
    new_stack = []

    for x,y in stack:
        if arr[x][y] == '#':
            continue
        for i in range(9):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<8 and 0<=ny<8 and arr[nx][ny] == '.' and visited[nx][ny]:
                new_stack.append((nx,ny))
                visited[nx][ny] = False
    
    if (0,7) in new_stack:
        result = 1
        break


    wall = wall_move(wall)

    stack = new_stack[:]

print(result)

import sys

input = sys.stdin.readline
def calc_operator(operator,x,y):
    if operator == '*':
        return x*y
    elif operator == '-':
        return x-y
    elif operator == '+':
        return x+y


def calc():
    new_num_list = []
    new_operator_list = []
    ind = 0
    while ind<len(num_list):
        if ind < len(num_list)-1:
            if not open_bracket[ind]:
                new_num_list.append(num_list[ind])
                new_operator_list.append(operator_list[ind])
                ind += 1
            else:
                new_number = calc_operator(operator_list[ind],num_list[ind],num_list[ind+1])
                if ind == len(num_list)-2:
                    new_num_list.append(new_number)
                else:
                    new_num_list.append(new_number)
                    new_operator_list.append(operator_list[ind+1])
                ind += 2
        else:
            new_num_list.append(num_list[ind])
            ind+= 1
    ind = 0
    value = new_num_list[0]
    while ind < len(new_num_list)-1:
        value = calc_operator(new_operator_list[ind],value,new_num_list[ind+1])
        ind += 1
    return value







def dfs(index):
    global result
    if index == len(num_list)-1:
        result = max(calc(),result)
        return
    else:
        if visited[index]:
            visited[index] = False
            visited[index+1] = False
            open_bracket[index] = True
            dfs(index+1)
            visited[index] = True
            visited[index+1] = True
            open_bracket[index] = False
        dfs(index+1)

N = int(input())
arr = list(input())
if N == 1:
    print(arr[0])
else:
    num_list = []
    operator_list = []
    for i in range(N):
        if i%2:
            operator_list.append(arr[i])
        else:
            num_list.append(int(arr[i]))
    result = -float('inf')
    visited = [True]*len(num_list)
    open_bracket = [False]*len(num_list)
    dfs(0)
    print(result)

import sys

input = sys.stdin.readline
def calc(operator,x,y):
    if operator == '*':
        return x*y
    elif operator == '-':
        return x-y
    elif operator == '+':
        return x+y
def dfs(idx,value):
    global result
    if idx == length_num-1:
        result = max(result,value)
        return
    temp = calc(operator_list[idx],value,num_list[idx+1])
    dfs(idx+1,temp)

    if idx < length_num-2:
        next_value = calc(operator_list[idx+1],num_list[idx+1],num_list[idx+2])
        temp = calc(operator_list[idx],value,next_value)
        dfs(idx+2,temp)



N = int(input())
origin_input = list(input().strip())
num_list = []
operator_list = []

for ind in range(len(origin_input)):
    if ind%2:
        operator_list.append(origin_input[ind])
    else:
        num_list.append(int(origin_input[ind]))
result = -float('inf')
length_num = len(num_list)

dfs(0,num_list[0])
print(result)

import sys
input = sys.stdin.readline
def check(num):
    visited[num] = True
    stack = [num]

    while stack:
        node = stack.pop(0)

        for next_node in tree[node]:
            if tree[node][next_node] == 1:
                if not visited[next_node]:
                    visited[next_node] = True
                    stack.append(next_node)
                    tree[node][next_node] = 0
                    tree[next_node][node] = 0
                else:
                    return False
    return True
            


tc = 1
while True:
    N,M = map(int,input().split())
    if N+M == 0:
        break
    parent_cnt = [0]*(N+1)
    tree = [{} for _ in range(N+1)]
    for _ in range(M):
        x,y = map(int,input().split())
        tree[x][y] = 1
        tree[y][x] = 1
    cnt = 0
    visited = [False]*(N+1)
    for num in range(1,N+1):
        if not visited[num]:
            if check(num):
                cnt += 1
    if cnt == 0:
        print(f'Case {tc}: No trees.')
    elif cnt == 1:
        print(f'Case {tc}: There is one tree.')
    else:
        print(f'Case {tc}: A forest of {cnt} trees.')


    tc += 1

def find_prime_number():
    global N
    numbers = [True]*(N+1)
    numbers[0] = False
    numbers[1] = False

    for num in range(2,N+1):
        if numbers[num]:
            for num_multi in range(num*2,N+1,num):
                numbers[num_multi] = False
    prime_number = []
    for num in range(N+1):
        if numbers[num]:
            prime_number.append(num)
    return prime_number



N = int(input())


prime_numbers = find_prime_number()
DP = [0]*40001



DP[0] = 1
for prime_number in prime_numbers:
    for num in range(prime_number,N+1):
        DP[num] = (DP[num]+DP[num-prime_number])%123456789


print(DP[N])

from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline
N, D,K,C = map(int,input().split())
a = defaultdict(int)

sushi = deque()
max_value = 0
# D 초밥의 가짓수
# K 는 연속해서 먹은 초밥의 수
# C 쿠폰번호
sushi_dict = defaultdict(int)
cnt = 0
sushi_list = [int(input()) for _ in range(N)]
for left in range(N+K+1):
    sushi_input = sushi_list[left%N]
    if len(sushi)<K:
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if len(sushi) == K:
            if sushi_dict[C]>0:
                max_value = max(max_value,cnt)
            else:
                max_value = max(max_value,cnt+1)
    else:
        remove_sushi = sushi.popleft()
        sushi_dict[remove_sushi] -= 1
        if sushi_dict[remove_sushi] == 0:
            cnt -= 1
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if sushi_dict[C]>0:
            max_value = max(max_value,cnt)
        else:
            max_value = max(max_value,cnt+1)

print(max_value)

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)

1

import sys

input = sys.stdin.readline

def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)
    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]


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

make_set = [i for i in range(N+1)]
rank =  [1 for _ in range(N+1)]
for _ in range(M):
    command, A,B = map(int,input().split())

    if command:
        if find_parent(A) == find_parent(B):
            sys.stdout.write('YES\n')
        else:
            sys.stdout.write('NO\n')
    else:
        union(A,B)