one Book a Day

평범한 이분탐색을 이용한 LIS import sys input = sys.stdin.readline from bisect import bisect_left N = int(input()) cards = list(map(int, input().split())) LIS = [0] for card in cards: if card > LIS[-1]: LIS.append(card) else: LIS[bisect_left(LIS,card)] = card print(len(LIS)-1)

겹치는 구간이 몇개냐 세주면 된다. def count_bus(n): bus_stops = [0 for _ in range(5000)] for _ in range(n): start, end = map(int,input().split()) for i in range(start-1,end): bus_stops[i] += 1 P = int(input()) qa_set = [] for i in range(P): qa_set.append(bus_stops[int(input())-1]) return qa_set for test in range(1, int(input())+1): N = int(input()) answer = count_bus(N) print(f'#{test}', end=' ') print(*answer)

문자열이 다 빌때까지 제거하며 더해줬다. def read_vertical(s): answer = '' cnt = 0 while cnt

예전 강의실 배정문제처럼 풀었다. round가 반올림이 아니라 사사오입이라는걸 깨달은 아주 소중한문제.. 내 한시간.. from heapq import heappop,heappush from math import ceil def find_time_units(n): students = [] for _ in range(n): start, end = map(int,input().split()) if start > end: start, end = end, start start = ceil(start/2) end = ceil(end/2) students.append([start,end]) students.sort() time_units = [] heappush(time_units,students[0][1]) fo..

가로 세로 박스 총 9개지점에서 검사해줬따. import sys input = sys.stdin.readline def check(x,y,matrix): col_check_box = {i:False for i in range(1,10)} row_check_box = {i:False for i in range(1,10)} box_check = {i:False for i in range(1,10)} # 행 검사 for num in matrix[x]: if not col_check_box[num]: col_check_box[num] = True else: return False # 열 검사 for j in range(9): num = matrix[j][y] if not row_check_box[num]: ro..

배열회전 너무 잘써먹는듯.. 대신 사고가 좀 갇히는것 같기도 하다. 다른 방법도 많은데 import sys input = sys.stdin.readline def rotate_clock(n, matrix): rot90 = [k[::-1] for k in zip(*matrix)] rot180 = [k[::-1] for k in zip(*rot90)] rot270 = [k[::-1] for k in zip(*rot180)] merge_matrix = [[] for _ in range(n)] for matrix in rot90,rot180,rot270: for i in range(n): merge_matrix[i].append(''.join(map(str,matrix[i]))) return merge_matr..

뒤에서부터 작은걸 만나면 그 차이만큼 결과에 더해줍니다. for test in range(1,int(input())+1): N = int(input()) prices = list(map(int, input().split())) answer = 0 max_price = 0 for j in range(N-1,-1,-1): if max_price > prices[j]: answer += max_price - prices[j] else: max_price = prices[j] print(f'#{test} {answer}')

널리 알려진대로 dp이용해서 풀이. import sys input = sys.stdin.readline def stick_paper(n): length = n//10 dp = [0] * (length+1) dp[0],dp[1] = 1,1 for i in range(2,length+1): dp[i] = dp[i-2]*2 + dp[i-1] return dp[length] for test in range(1,int(input())+1): print(f'#{test} {stick_paper(int(input()))}')

stack을 이용해 같은게 옆에있으면 같이 빼버린다. def repeat_str(s): init = len(s) stack = [] cnt = 0 while s: pre = s.pop() if stack: if pre == stack[-1]: stack.pop() cnt += 1 else: stack.append(pre) else: stack.append(pre) return init - 2*cnt for test in range(1,int(input())+1): s = list(input()) print(f'#{test} {repeat_str(s)}')

단방향 그래프 dfs 탐색 def find_path(s,g): global answer if s==g: answer = 1 return for next_node in graph[s]: if not visited[next_node]: visited[next_node] = True find_path(next_node,g) for test in range(1,int(input())+1): V, E = map(int,input().split()) graph = {i:[] for i in range(1,V+1)} answer = 0 visited = {i:False for i in range(1,V+1)} for _ in range(E): a, b = map(int,input().split()) graph[a] ..