one Book a Day

평범한 DFS로 col_check해주면서 진행. 여기서 더 발전되면 비숍, 룩, 퀸 배치문제로 넘어간다. def DFS(row,sum_nums): global min_sum if row == N: min_sum = min(min_sum,sum_nums) return if sum_nums > min_sum: return for i in range(N): if not col_check[i]: col_check[i] = True DFS(row+1,sum_nums+matrix[row][i]) col_check[i] = False for test in range(1,int(input())+1): N = int(input()) matrix = [list(map(int,input().split())) for _ in..

평범한 2차원 그래프 탐색. from collections import deque def BFS(x,y): visited = [[-1]*N for _ in range(N)] visited[x][y] = 0 queue = deque() queue.append([x,y]) while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

deque rotate써서 그냥 돌려줬다. 안돌려도 풀수있을것같긴한데 귀찮.. from collections import deque for test in range(1,int(input())+1): N, M = map(int, input().split()) pizzas = list(map(int,input().split())) pizzas_idx = [[pizza,idx+1] for idx, pizza in enumerate(pizzas)] oven = deque() # 오븐의 크기 N for pizza in pizzas_idx: oven.append(pizza) while len(oven) == N: oven.rotate(-1) oven[-1][0] //=2 if not oven[-1][0]: oven..

평범한 그래프 탐색. from collections import deque def BFS(start,goal): queue = deque() queue.append([start,0]) visited = {i: False for i in range(1,V+1)} visited[start] = True while queue: cur_node, cur_dist = queue.popleft() if cur_node==goal: return cur_dist for next_node in graph[cur_node]: if not visited[next_node]: visited[next_node] = True queue.append([next_node,cur_dist+1]) return 0 for test in ..

그냥 나머지 for test in range(1,int(input())+1): N, M = map(int, input().split()) arr = list(map(int, input().split())) print(f'#{test} {arr[M%N]}')

각 업무의 limit마다 누적 시간 합과 limit을 비교해주면서 최솟값을 가져가면 된다. limit을 초과하면 즉시종료 import sys input = sys.stdin.readline N = int(input()) works = [list(map(int, input().split())) for _ in range(N)] works = sorted(works,key = lambda x: x[1]) total_time = 0 min_rest = float('inf') for time, limit in works: total_time += time min_rest = min(min_rest, limit-total_time) if limit < total_time: print(-1) exit() print..

문자열 덧셈. 매개변수로 주고 dfs import sys input = sys.stdin.readline def DFS(sum_num, answer): global cnt if sum_num > n: return if n == sum_num: cnt += 1 if cnt == k: print(answer[:-1]) exit() for i in (1, 2, 3): DFS(sum_num + i, answer+str(i)+'+') cnt = 0 n, k = map(int, input().split()) DFS(0, '') print(-1)

간격 컨트롤이 아닌 내부 요소들의 합으로 컨트롤하는 슬라이딩 윈도우. import sys input = sys.stdin.readline N = int(input()) prex_sum, left = 0, 0 answer = 0 # 슬라이딩 윈도우 for right in range(1,N+1): # 결론적으로 end는 기존 슬라이딩 윈도우 처럼 일정 간격이 고정이 아니라 # 일정 합 이상이되면 알아서 그 간격이 줄어드는 시스템이므로 한번 순회로 전부 조사 가능. while left < N and prex_sum < N: prex_sum += left+1 left += 1 if prex_sum == N: answer += 1 prex_sum -= right print(answer)

stack란에 있어서 억지로 stack처럼 LIFO구현. 조금 더 만지면 복사안하고 stack2개로 돌릴 수 있을 것같은데 그냥 구상만.. import sys sys.stdin = open('input.txt') test = int(input()) for test in range(1, test+1): n = int(input()) pascals = [[] for _ in range(n)] #* *삼각형을 그릴 틀* pascals[0].append(1) #* *첫열은 그냥 삽입* for i in range(1, n): #* *2열부터 그릴 것임.* stack = pascals[i-1][:] #* *1열(i-1열을 복사)* pascals[i].append(1) #* *첫인자 삽입* for j in range..

stack을 이용 간단풀이. import sys sys.stdin = open('input.txt') for test in range(1,11): s, nums = input().split() nums = list(nums) # 비밀번호 list stack = [] # 옮겨담을 stack while nums: stack.append(nums.pop()) # 일단 pop while nums and stack and stack[-1] == nums[-1]: # 같은 문자가 나오면 양쪽 다 제거. 틀린게 나올때까지 혹은 빌때까지 stack.pop() nums.pop() print(f"#{test} {''.join(stack)[::-1]}") # stack 에 역순으로 담긴 password 뒤집어 출력