one Book a Day

유니온 파인드. 정순, 역순으로 오르막길 포함된 갯수 파악해서 연산. import sys input = sys.stdin.readline def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(a,b): a = find(a) b = find(b) if level[a] >= level[b]: parent[b] = a if level[a]==level[b]: level[a] +=1 else: parent[a] = b N, M = map(int, input().split()) parent = {i:i for i in range(N+1)} level = {i:0 for i in range(N+1)..

오랜만에 직사각형 누적합 import sys input = sys.stdin.readline N, M = map(int, input().split()) areas = [list(map(int, input().split())) for _ in range(N)] K = int(input()) dp = [[0 for _ in range(M+1)] for _ in range(N+1)] dp[1][1] = areas[0][0] for i in range(1,N+1): for j in range(1,M+1): dp[i][j] = dp[i-1][j] + dp[i][j-1] + areas[i-1][j-1] - dp[i-1][j-1] for _ in range(K): x1,y1,x2,y2 = map(int, input(..

그냥 성별조건 추가된 크루스칼 import sys input = sys.stdin.readline def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(a,b): a = find(a) b = find(b) if level[a] >= level[b]: parent[b] = a if level[a]==level[b]: level[a] +=1 else: parent[a] = b N, M = map(int, input().split()) sex = [0] + list(input().split()) arr = [] parent = {i:i for i in range(1,N+1)} level = {..

경우의 수 따라 진입 하면 된다. 주의할 점은 for 문 순회기 때문에 key를 0으로 바꿔 넣으면 다시 1로 바꿔주어야 한다는 것. 분기 문제일때 변수를 직접 바꾸는 것은 주의하자. import sys input = sys.stdin.readline from collections import deque def bfs(): queue = deque() queue.append([s_x-1,s_y-1,0,1]) visited = [[[False for _ in range(M)] for _ in range(N)] for _ in range(2)] visited[1][s_x-1][s_y-1] = True while queue: x,y,time,key = queue.popleft() if x==t_x-1 and ..

경로에 대한 조사는 둘중하나다. 같이 들고 다니던가. 아니면 pre_node 배열을 만들던가. import sys input = sys.stdin.readline from collections import deque def bfs(start,target): queue = deque() queue.append([start,0,[start]]) visited = [False]*400001 visited[start] = True while queue: cur,cur_time,cur_path = queue.popleft() if cur==target: return cur_time ,cur_path for next_node in (cur-1,cur+1,cur*2): if 0

에라토스테네스의 seive 써서 구했다. 모든 숫자를 최댓 범위의 제곱근 범위까지 돌며 그 배수를 False로 바꿔주는게 포인트. i는 False로 바꾸지 않는다(소수이기 때문) i+i부터 바꾼다. import sys input = sys.stdin.readline def che(): nums = [True]*(N+1) nums[0]=nums[1]=False primes = [] for i in range(2,int(N**0.5)+1): if nums[i]: for j in range(i+i, N+1, i): nums[j] = False return [i for i in range(M,N+1) if nums[i]] M = int(input()) N = int(input()) arr = che() if a..

방향, 거리에따른 위치 변환 후 계산 import sys input = sys.stdin.readline N, M = map(int, input().split()) K = int(input()) store = [] for _ in range(K): store_dir, dist = map(int, input().split()) if store_dir==1: y = M x = dist elif store_dir==2: y=0 x = dist elif store_dir==3: x=0 y=M-dist else: x=N y = M-dist store.append([x,y]) dongguen_dir, dist = map(int, input().split()) if dongguen_dir==1: y = M x = d..

반대로 넣고 뒤집었습니다. import sys input = sys.stdin.readline N = int(input()) arr = list(map(int,input().split())) answer = [] for i in range(1,N+1): answer.insert(arr[i-1],i) print(*answer[::-1])

카드 숫자 센다음 큰 숫자부터 갯수 비교 import sys input = sys.stdin.readline N = int(input()) for _ in range(N): a_cnt = [0]*5 b_cnt = [0]*5 a_n, *a_card = map(int, input().split()) b_n, *b_card = map(int, input().split()) for card in a_card: a_cnt[card] += 1 for card in b_card: b_cnt[card] += 1 for i in range(1,5): if a_cnt[-i] > b_cnt[-i]: print('A') break elif a_cnt[-i] < b_cnt[-i]: print('B') break else: pr..

학생 배열에 저장하고 K의 몫만큼 방 할당. 나머지있으면 하나더 할당 import sys input = sys.stdin.readline N, K = map(int, input().split()) students = [[0,0] for _ in range(6)] for _ in range(N): S, Y = map(int, input().split()) students[Y-1][S] += 1 answer = 0 for grade in students: for sex in grade: answer += sex//K if sex%K: answer += 1 print(answer)