one Book a Day

아이디어 1. 추 무게의 합을 전부 구해서 dp에 체크 2. 모든 무게에 다시한번 추를 빼주며(반대쪽 저울에 올려놓으며) dp체크 사실 같은 추를 두번사용하는 즉 왼쪽에도 오른쪽에도 올려놓는 경우를 체크하기는 하나 양쪽에 올려봤자 안올렸을 때의 dp와 같으므로 문제없다. (같은걸 두번 더하거나 두번뺄때가 아니면 결과 집합은 같다.) import sys input = sys.stdin.readline chu_N = int(input()) chu_list = list(map(int,input().split())) glass_ball_N = int(input()) ball_list = list(map(int,input().split())) dp_chu = {i:False for i in range(sum(ch..

숨바꼭질보다 조금 쉬운 하위문제 느낌? 어차피 이동의 모든 가중치는 같으므로 따로 우선순위큐나 appendleft없이 차례로 탐색하면 된다. 어차피 먼저 도착하면 먼저 출력된다. import sys input = sys.stdin.readline from collections import deque def BFS(F,S,G,U,D): dp_count = {i:float('inf') for i in range(1,F+1)} dp_count[S] = 0 queue = deque() queue.append(S) while queue: cur_stair = queue.popleft() if cur_stair == G: print(dp_count[G]) return for next_stair in (cur_sta..

루트노드를 줬으니 루트노드부터 BFS로 전위순회 하며 부모를 기록해줬다. import sys input = sys.stdin.readline from collections import deque # BFS로 루트부터 전위순회. def BFS(start): queue = deque() visited = [False]*(N+1) visited[start] = True queue.append(start) while queue: cur_node = queue.popleft() for next_node in graph[cur_node]: if not visited[next_node]: visited[next_node] = True super_node[next_node] = cur_node queue.append(..

set을 이용하는 문제로 set 삽입, 삭제 메소드인 add remove discard만 알면 무난한 코드로 풀린다. import sys input = sys.stdin.readline m = int(input()) S = set() for _ in range(m): commands = input().strip().split() # split()을 통해 띄어씌기가 있으면 튜플인 commands # 없으면 그냥 commands if len(commands) == 1: if commands[0] == "all": S = set([i for i in range(1, 21)]) else: S = set() # set은 add remove discard(discard는 없는거 없애려해도 오류아냄.) else: c..

후위, 중위순회로 전위순회 찾기. 후위순회의 마지막 순회가 루트노드인 것을 이용 그 루트노드를 기준으로 좌우로 찢을 수 있었다. 인덱싱을 위해 최초 인덱스로 부터 중위순회로 얻은 left,right값으로 트리를 좌우로 분할하면서도 인덱싱이 가능하게 설계. 두세번 코드해석해봤는데 아직도 혼자 설계하라면 할수있을까 싶다. import sys sys.setrecursionlimit(10**6) n = int(input()) in_order = list(map(int, input().split())) post_order = list(map(int, input().split())) pos = [0]*(n+1) for i in range(n): pos[in_order[i]] = i # 중위 순회로 부모노드의 위치에..

부분집합은 조합툴쓰면 너무 편하다.. 자모음 cnt해서 조건 만족하면 정답 리스트에 넣었다. import sys input = sys.stdin.readline from itertools import combinations L,C = map(int,input().split()) secret = list(input().split()) # 암호는 사전순 sorted되어있다. secret.sort() # 최소한개모음 두개자음 mom_char = ['a','e','i','o','u'] combs = list(combinations(secret,L)) ans = [] for chars in combs: mom_cnt=0 child_cnt=0 for char in chars: if char in mom_char: ..

DFS하니까 재귀에러나고 시간초과 메모리초과 가관이어서 BFS로 다시 풀었다. 구조는 똑같이 queue에 1을 넣고 1부터 위에서 아래로 탐색하며 parent값을 자식들에게 할당하는 방식. import sys input = sys.stdin.readline from collections import defaultdict,deque N = int(input()) graph = defaultdict(list) for _ in range(N-1): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a) queue = deque([1]) ans = {} check = [False for _ in range(N+1)] while queue: pa..

항상 문자열에서 검사하고 중복 갯수세고 하는거 나오면 set()으로 목록 만들고 ord써서 반복문 돌릴수 있게 설계한다거나 char_count 배열에 갯수 저장해 넣고 뺄때 쓸 수 있게 설계. string ='' 두고 더하고 빼고 슬라이싱 인덱싱 하는 스킬 더 기를 것. 문자열로 DFS돌리는 문제 은근 나옴. 슬라이싱으로 두문자씩, 두숫자씩 묶거나 숫자문자면 중간중간 int써서 수식계산 및 비교 까지 가능. 진법변환까지는 아직 문제못봄. from sys import stdin input = stdin.readline def dfs(depth, string): global N, cnt if depth == N: # print(string) cnt += 1 return # 종류별로 알파뱃 검사(깊이마다) f..

강의실의 갯수N = queue의 방의 갯수. 최소 heap을 사용해 가장 빨리 돌아오는 수업 종료시간보다 시작해야하는 수업이 빠르면 방 하나 증가 적으면 끝난수업빼고 새수업 넣는다. 즉 최대 필요한 room의갯수가 계속유지된다. 최솟값, 최댓값을 계속 뽑아내야 할때는 heapq.. 잘 생각해보자 import heapq import sys N = int(input()) timeTable = [list(map(int,sys.stdin.readline().split())) for _ in range(N)] timeTable.sort(key=lambda x: x[0]) queue = [] heapq.heappush(queue,timeTable[0][1]) for i in range(1,N): # last_tim..

싸이클을 만들 수 있느냐는 문제 조건은 1. 이전칸으로 가지 않을 것 2. 이전칸을 제외하고 방문했던 지점을 만나면 싸이클이 존재. N,M=map(int,input().split()) matrix=[list(map(str,input()))for _ in range(N)] visited = [[False]*M for _ in range(N)] dy=[0,0,1,-1] dx=[1,-1,0,0] # 싸이클의 조건 # 1. 바로 이전 칸으로 가지 말 것( 이전 좌표 가억해두고 같으면 이동하지말것.) # 2. 그럼에도 불구하고 갔던 곳(visited true)를 만나면 싸이클이 존재하므로 True를 반환할것. def dfs(x,y,px,py,ball): if visited[x][y]==True: return Tr..